华为OD机试_2025 B卷_区间交集（Python，100分）（附详细解题思路）

题目描述

给定一组闭区间，其中部分区间存在交集。

任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为[3,5])。

公共区间之间若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。

按升序排列输出合并后的区间列表。

输入描述
一组区间列表，

区间数为 N: 0<=N<=1000;

区间元素为 X: -10000<=X<=10000。

输出描述
升序排列的合并区间列表

备注
区间元素均为数字，不考虑字母、符号等异常输入。
单个区间认定为无公共区间。
用例

区间公共区间合并问题：算法详解与实现

核心解题思路

题目要求找出所有区间对的公共区间，然后将这些公共区间合并后按升序输出。核心思路可分为三步：

1. 生成所有公共区间：对于给定的N个区间，计算每两个不同区间之间的公共区间（交集）
2. 合并公共区间：将重叠的公共区间合并为更大的连续区间
3. 输出结果：按升序排列输出合并后的区间列表

关键算法：区间合并

区间合并是解决此类问题的核心技术：

1. 将所有区间按左端点排序
2. 依次处理每个区间：
   • 如果当前区间与结果列表中最后一个区间重叠，则合并
   • 否则将当前区间加入结果列表

完整解题过程

步骤1：生成所有公共区间

对于每对不同的区间[a,b]和[c,d]，它们的公共区间为：

left = max(a, c)
right = min(b, d)

当且仅当left ≤ right时，[left, right]是有效公共区间

步骤2：合并公共区间

1. 将所有公共区间按左端点升序排序
2. 初始化合并结果列表
3. 遍历每个公共区间：
   • 如果结果列表为空或当前区间与最后一个区间不重叠，直接添加
   • 否则合并当前区间到最后一个区间

步骤3：输出结果

• 如果没有公共区间，输出"None"
• 否则按行输出每个合并后的区间，每行格式为"左端点 右端点"

代码实现

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print("None")
        return
    
    n = int(data[0])
    intervals = []
    index = 1
    for i in range(n):
        # 读取每个区间的起点和终点
        start = int(data[index])
        end = int(data[index + 1])
        index += 2
        intervals.append((start, end))
    
    # 存储所有公共区间
    common_intervals = []
    
    # 生成所有两两区间的公共区间
    for i in range(n):
        for j in range(i + 1, n):
            a, b = intervals[i]
            c, d = intervals[j]
            # 计算公共区间的左右端点
            left = max(a, c)
            right = min(b, d)
            # 检查是否有效
            if left <= right:
                common_intervals.append((left, right))
    
    # 如果没有公共区间
    if not common_intervals:
        print("None")
        return
    
    # 按左端点排序
    common_intervals.sort(key=lambda x: x[0])
    
    # 合并公共区间
    merged = []
    current_start, current_end = common_intervals[0]
    
    for i in range(1, len(common_intervals)):
        start, end = common_intervals[i]
        # 检查是否与当前区间重叠
        if start <= current_end:
            # 合并区间
            current_end = max(current_end, end)
        else:
            # 保存当前合并区间
            merged.append((current_start, current_end))
            # 开始新区间
            current_start, current_end = start, end
    
    # 添加最后一个区间
    merged.append((current_start, current_end))
    
    # 输出结果
    for start, end in merged:
        print(f"{start} {end}")

if __name__ == "__main__":
    main()

实例解析

样例1：输入4个区间 [0,3], [1,3], [3,5], [3,6]

1. 生成公共区间：

   [0,3] & [1,3] → [1,3]
   [0,3] & [3,5] → [3,3]
   [0,3] & [3,6] → [3,3]
   [1,3] & [3,5] → [3,3]
   [1,3] & [3,6] → [3,3]
   [3,5] & [3,6] → [3,5]
   

2. 公共区间列表：[[1,3], [3,3], [3,3], [3,3], [3,3], [3,5]]

3. 合并过程：

   • 排序后：[1,3], [3,3], [3,3], [3,3], [3,3], [3,5]
   • 合并：

     [1,3] + [3,3] → [1,3] (右端点不变)
     [1,3] + [3,3] → [1,3]
     [1,3] + [3,3] → [1,3]
     [1,3] + [3,3] → [1,3]
     [1,3] + [3,5] → [1,5] (合并)
     

4. 输出：1 5

样例2：输入4个区间 [0,3], [1,4], [4,7], [5,8]

1. 生成公共区间：

   [0,3] & [1,4] → [1,3]
   [0,3] & [4,7] → 无
   [0,3] & [5,8] → 无
   [1,4] & [4,7] → [4,4]
   [1,4] & [5,8] → 无
   [4,7] & [5,8] → [5,7]
   

2. 公共区间列表：[[1,3], [4,4], [5,7]]

3. 合并过程：三个区间互不重叠，保持原样

4. 输出：

   1 3
   4 4
   5 7
   

样例3：输入2个区间 [1,2], [3,4]

• 无公共区间
• 输出：None

关键点说明

1. 公共区间生成：

   left = max(a, c)
   right = min(b, d)
   if left <= right:  # 有效公共区间
   

2. 区间合并核心逻辑：

   if start <= current_end:  # 重叠
       current_end = max(current_end, end)
   else:  # 不重叠
       merged.append((current_start, current_end))
       current_start, current_end = start, end
   

3. 边界情况处理：

   • 无公共区间 → 输出"None"
   • 单个公共区间 → 直接输出
   • 完全重叠区间 → 合并为大区间

扩展思考

实际应用场景

1. 时间调度系统：合并重叠会议时间
2. 资源分配优化：合并相邻资源块
3. 基因序列分析：合并重叠基因片段
4. 网络路由优化：合并相邻IP地址段

算法变体

1. 增量合并：动态添加区间时实时合并
2. 并行处理：分治法加速大规模区间合并
3. 多维扩展：将算法扩展到二维或多维空间
4. 概率模型：考虑区间权重或置信度

区间合并算法是计算机科学中的基础技术，掌握它能解决各种实际工程问题。理解核心思想后，可以灵活应用到不同领域的数据处理任务中。