华为OD机试_2025 B卷_区间交集（Python，100分）（附详细解题思路）
文章目录
- 题目描述
- 区间公共区间合并问题：算法详解与实现
- 核心解题思路
- 关键算法：区间合并
- 完整解题过程
- 步骤1：生成所有公共区间
- 步骤2：合并公共区间
- 步骤3：输出结果
- 代码实现
- 实例解析
- 样例1：输入4个区间 [0,3], [1,3], [3,5], [3,6]
- 样例2：输入4个区间 [0,3], [1,4], [4,7], [5,8]
- 样例3：输入2个区间 [1,2], [3,4]
- 关键点说明
- 扩展思考
- 实际应用场景
- 算法变体
题目描述
给定一组闭区间，其中部分区间存在交集。
任意两个给定区间的交集，称为公共区间(如:[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。
输出描述
升序排列的合并区间列表
备注
区间元素均为数字，不考虑字母、符号等异常输入。
单个区间认定为无公共区间。
用例
| 输入 | 4 0 3 1 3 3 5 3 6 |
| 输出 | 1 5 |
| 说明 | [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]， 公共区间列表为[[1,3],[3,3],[3,5]]； [1,3],[3,3],[3,5]存在交集，须合并为[1,5]。 |
| 输入 | 4 |
| 输出 | 1 3 4 4 5 7 |
| 说明 | 无 |
| 输入 | 2 |
| 输出 | None |
| 说明 | [1,2]和[3,4]无交集 |
区间公共区间合并问题：算法详解与实现
核心解题思路
题目要求找出所有区间对的公共区间，然后将这些公共区间合并后按升序输出。核心思路可分为三步：
- 生成所有公共区间：对于给定的N个区间，计算每两个不同区间之间的公共区间（交集）
- 合并公共区间：将重叠的公共区间合并为更大的连续区间
- 输出结果：按升序排列输出合并后的区间列表
关键算法：区间合并
区间合并是解决此类问题的核心技术：
- 将所有区间按左端点排序
- 依次处理每个区间：
- 如果当前区间与结果列表中最后一个区间重叠，则合并
- 否则将当前区间加入结果列表
完整解题过程
步骤1：生成所有公共区间
对于每对不同的区间[a,b]和[c,d]，它们的公共区间为：
left = max(a, c)
right = min(b, d)
当且仅当left ≤ right时，[left, right]是有效公共区间
步骤2：合并公共区间
- 将所有公共区间按左端点升序排序
- 初始化合并结果列表
- 遍历每个公共区间：
- 如果结果列表为空或当前区间与最后一个区间不重叠，直接添加
- 否则合并当前区间到最后一个区间
步骤3：输出结果
- 如果没有公共区间，输出"None"
- 否则按行输出每个合并后的区间，每行格式为"左端点 右端点"
代码实现
def main():import sysdata = sys.stdin.read().split()if not data:print("None")returnn = int(data[0])intervals = []index = 1for i in range(n):# 读取每个区间的起点和终点start = int(data[index])end = int(data[index + 1])index += 2intervals.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]
-
生成公共区间：
[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] -
公共区间列表：
[[1,3], [3,3], [3,3], [3,3], [3,3], [3,5]] -
合并过程：
- 排序后：
[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] (合并)
- 排序后：
-
输出：
1 5
样例2：输入4个区间 [0,3], [1,4], [4,7], [5,8]
-
生成公共区间：
[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] -
公共区间列表：
[[1,3], [4,4], [5,7]] -
合并过程：三个区间互不重叠，保持原样
-
输出：
1 3 4 4 5 7
样例3：输入2个区间 [1,2], [3,4]
- 无公共区间
- 输出：
None
关键点说明
-
公共区间生成：
left = max(a, c) right = min(b, d) if left <= right: # 有效公共区间 -
区间合并核心逻辑：
if start <= current_end: # 重叠current_end = max(current_end, end) else: # 不重叠merged.append((current_start, current_end))current_start, current_end = start, end -
边界情况处理：
- 无公共区间 → 输出"None"
- 单个公共区间 → 直接输出
- 完全重叠区间 → 合并为大区间
扩展思考
实际应用场景
- 时间调度系统：合并重叠会议时间
- 资源分配优化：合并相邻资源块
- 基因序列分析：合并重叠基因片段
- 网络路由优化：合并相邻IP地址段
算法变体
- 增量合并：动态添加区间时实时合并
- 并行处理：分治法加速大规模区间合并
- 多维扩展：将算法扩展到二维或多维空间
- 概率模型：考虑区间权重或置信度
区间合并算法是计算机科学中的基础技术，掌握它能解决各种实际工程问题。理解核心思想后，可以灵活应用到不同领域的数据处理任务中。