区间合并
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 / 常见坑
排序键选错。
合并用
start 排序;贪心保留尽量多不重叠区间用 end 排序。 两者不能互换 —— 按终点排序后,上面的合并循环会漏掉跨越早期区间的重叠。「严格重叠」与「非严格重叠」。
[1, 3] 和 [3, 5] 算重叠吗?题目读两遍。算端点相接时, 合并条件是 result.last.end ≥ s;不算时是 result.last.end > s。 搞混了就翻答案。在不该原地改动时原地改动。
这个模式天然就像原地扫描:弹出、比较、合并到前一段、压入。方便 —— 但调用方之后还要用
intervals 的话,你已经悄悄毁掉了它的数据。先复制。05 / 去 LeetCode 上练习
中等16
01Merge Intervals— LC 56→02Insert Interval— LC 57→03Meeting Rooms II— LC 253→04Non-overlapping Intervals— LC 435→05Minimum Number of Arrows to Burst Balloons— LC 452→06Add Bold Tag in String— LC 616→07Maximum Length of Pair Chain— LC 646→08My Calendar II— LC 731→09Partition Labels— LC 763→10Interval List Intersections— LC 986→11Video Stitching— LC 1024→12Car Pooling— LC 1094→13Remove Interval— LC 1272→14Remove Covered Intervals— LC 1288→15Divide Intervals Into Minimum Number of Groups— LC 2406→16Count Ways to Group Overlapping Ranges— LC 2580→
困难9
01The Skyline Problem— LC 218→02Data Stream as Disjoint Intervals— LC 352→03Range Module— LC 715→04My Calendar III— LC 732→05Employee Free Time— LC 759→06Rectangle Area II— LC 850→07Maximum Profit in Job Scheduling— LC 1235→08Minimum Number of Taps to Open to Water a Garden— LC 1326→09Minimum Interval to Include Each Query— LC 1851→