区间合并
01 / 一句话本质
按起点排序,然后从左到右扫一遍 —— 每个区间要么把当前合并区间往右扩, 要么把它提交并另起一段新的。整个模式就在这一次比较里。
题目合并所有重叠区间输入[1,3] [2,6] [8,10] [15,18]
输入有 4 个区间。下方按原始顺序绘制各条。
步
0 / 12
当前段
—
结果
0
0 / 12
02 / 模式骨架
# 按起点排序后扫描intervals.sort(key=start)result ← []for [s, e] in intervals:if result 为空 or result.last.end < s:result.push([s, e]) # 提交新段else:result.last.end ← max(result.last.end, e) # 向右扩# 重叠判定:result.last.end ≥ s(按起点排序后)
03 / 什么时候用这个模式
"合并重叠区间"
最典型的信号。输出区间数至多等于输入数,通常更少。如果数量没变,说明这套模式只是在做一次检查。
"会议 / 预订 / 排程"
日历类问题:会议室、航班、员工空闲时间。区间天然带有时间轴的含义。
"在已排序区间中插入"
一种变体 —— 已排序区间列表中插入一个新区间。合并逻辑相同, 只是扫到新区间该插入的位置为止。
"删除最少区间使其不重叠"
贪心变体 —— 按终点排序而不是起点,数一下有多少必须丢掉。 排序键不同,扫描骨架相同。
04 / 常见坑
i.
排序键选错。
合并用
start 排序;贪心保留尽量多不重叠区间用 end 排序。 两者不能互换 —— 按终点排序后,上面的合并循环会漏掉跨越早期区间的重叠。ii.
「严格重叠」与「非严格重叠」。
[1, 3] 和 [3, 5] 算重叠吗?题目读两遍。算端点相接时, 合并条件是 result.last.end ≥ s;不算时是 result.last.end > s。 搞混了就翻答案。iii.
在不该原地改动时原地改动。
这个模式天然就像原地扫描:弹出、比较、合并到前一段、压入。方便 —— 但调用方之后还要用
intervals 的话,你已经悄悄毁掉了它的数据。先复制。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。