01先把问题说具体
合并闭区间 [1,3]、[2,6]、[8,10]、[10,12],得到覆盖相同点集合的最少连续区间。
02一步步得到方法
排序消除回头检查
先按左端点升序排序。扫描到新区间 [l,r] 时,如果 l≤当前区间右端点,就存在重叠或共享端点,将右端点更新为 max(old,r)。否则两者之间有空隙,当前区间可以安全输出。
max 不能省略:新区间可能完全包含在当前区间内部,比如 [1,10] 后接 [2,3],若直接把右端改成 3,会丢掉 3 到 10 的覆盖。
先声明端点规则
本课使用闭区间,所以 [1,2] 与 [2,3] 共享点 2,可合并。若题目是占用时段 [start,end),相接不等于同时占用;是否为了表示并集而仍合并相接区间,要由输出需求决定。
为什么只需记住最后一段
按左端点排序后,未来区间的起点不会更早。若当前区间与输出最后一段不相交,就更不可能跨过它去与更早的已结束区间相交,所以只比较最后一段即可。
是否把端点相等视为重叠取决于语义。闭区间 [1,2] 与 [2,3] 共享点;预约采用半开区间时,前一场在2结束、后一场在2开始可以不冲突。代码条件必须对应题意。
03把一个小例子完全算清楚
闭区间 [[1,3],[2,6],[8,10],[10,12]]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 读 [1,3] | 当前 [1,3] | 初始化 |
| 读 [2,6] | 当前 [1,6] | 2≤3,扩大右端 |
| 读 [8,10] | 输出 [1,6],当前 [8,10] | 8>6,中间有空隙 |
| 读 [10,12] | 当前 [8,12] | 共享端点 10 |
窄屏可左右滑动表格,阅读完整计算与理由。
结果 [[1,6],[8,12]];合并改变表示方式,不改变覆盖集合。
04为什么这个方法成立
- 当前区间始终是尚未输出的重叠链的完整并集。
- 新区间起点在右端之外时,后续起点只会更大,不可能再与当前区间连接。
- 因此输出后无需回头,最终每个区间被完整覆盖且结果互不重叠。
05把推导翻译成代码
Python · 可独立运行的教学实现
def merge_intervals(intervals):
result = []
for left, right in sorted(intervals):
assert left <= right
if not result or left > result[-1][1]:
result.append([left, right])
else:
result[-1][1] = max(result[-1][1], right)
return result逐个理解关键决定
sorted(intervals)- 扫描安全性来自左端点有序,不能直接套用原始顺序。
max(result[-1][1], right)- 同时处理延伸和包含两种关系。
06时间、空间与实现范围
排序 O(n log n),扫描 O(n),输出与排序副本最多 O(n) 空间。
如果输入已按左端点排序且可流式读取,合并本身只需一次线性扫描。
07改变条件,检查哪里会出错
把区间合并当作最大不重叠区间选择
前者保留全部覆盖,后者丢弃部分区间以最大化数量,目标不同。
直接修改调用者的区间列表
原地排序或复用内层列表会改变输入;若接口承诺保留输入,应复制需要修改的结构。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[[1,10],[2,3]] 输出什么?
需要一点提示
第二个被包含。
查看解析与答案
[[1,10]]。
闭区间 [2,2] 是否为空?
需要一点提示
左右端点都包含。
查看解析与答案
不是,包含点 2;与半开 [2,2) 不同。
如何计算合并后的总连续长度?
需要一点提示
对不重叠结果求差。
查看解析与答案
连续长度求 Σ(r−l);若统计整数点且闭区间不重叠,则求 Σ(r−l+1),先明确度量。