【LC 56】合并区间：排序把「可能重叠的对」压缩成「只比当前」
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个与输入区间数量最少的区间数组，且这些区间不重叠。
示例：[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]。
区间题家族的入口。它给的思维模板 ——
先把区间按端点排序，再线性扫一遍 —— 直接通向 435（删除最少区间）、452（最少的箭）、57（插入区间）等一整族题。
一、暴力为什么慢：重叠是" pairwise"的
判断两个区间
[a1,a2] 和
[b1,b2] 是否重叠，只要一句
a1 <= b2 && b1 <= a2。麻烦在于候选对的数量：n 个区间有
n(n-1)/2 对，合并产生的结果还会改变后续的比较对象，暴力做法又难写又慢（O(n²)）。
突破口是问一句：
两个"八竿子打不着"的区间，有必要互相比较吗？
二、排序之后的结构性免费
把区间按
左端点排序。设扫描到区间
[s, e] 时，前面已经合并出一个"当前合并区间"
[curStart, curEnd]。关键性质：
排序后，s 是目前见过的最大左端点。如果 s > curEnd，那么 [s,e] 和更早的任何区间都不可能重叠 —— 因为更早那些区间的 end 全都 <= curEnd（否则它们早就该被并进当前合并区间了）。
所以"和前面所有区间比一遍"可以塌缩成
只和当前合并区间比一次：
s <= curEnd → 够得着，延伸：curEnd = max(curEnd, e)；s > curEnd → 够不着，收段：当前合并区间进结果，[s,e] 开一段新的。
每个区间只参与一次判断，扫描是严格 O(n)；瓶颈全在排序的 O(n log n)。
总复杂度 O(n log n)，主要成本买断了后面所有判断的合法性。
2.1 动画与逐帧推演
官方例
[[1,3],[2,6],[8,10],[15,18]]（与状态机
mergeIntervalsSteps.js 的 7 帧实际输出逐行核对过）：
两个值得盯住的瞬间：
- 第 3 帧：
[2,6] 的 start 是 2，够得着当前区间 [1,3] 的 end 3 —— 延伸成 [1,6]。注意 end 取的是 max(3, 6) = 6。
- 第 4 帧：
[8,10] 的 start 8 > 6 —— 收段。此刻 [1,6] 永远定格：后面区间的 start 只会更大，再也不可能有区间够得着它。这就是"收段"这个词的确切含义。
三、三个必踩的坑
3.1 端点相触算重叠（<= 不是 <）
[1,4] 和
[4,5] 要合并成
[1,5] —— 题面的"重叠"包含
端点相触。所以判断是
s <= curEnd。写成
< 的话，
[1,4],[4,5] 会被错拆成两段：
这个 bug 和本系列反复出现的模式一样：官方样例恰好测不出来 —— 官方例里没有端点相触的区间。要自测，就用 [1,4],[4,5]。
3.2 延伸必须取 max，不能直接覆盖
当前区间
[1,6]，来一个
[2,3] —— start 2 <= 6，重叠；但它的 end 是 3，
比 curEnd 还小（整体被罩住）。直接
curEnd = 3 会把合并区间
缩回去，后面
[5,7] 就会被错误地拆开。正确写法：
cur_end = max(cur_end, e)
状态机的不变量测试专门钉了这条：
每一帧里，所有已处理区间都必须被"当前合并区间 ∪ 已收结果"覆盖 —— 用
[1,10],[2,3],[4,5],[6,7]（四个区间并成一段）验证。
3.3 结果要新造数组，别污染输入
结果里的区间如果是输入区间的
引用（比如直接
result.append(cur) 之后又去改
cur[1]），调用方的原数据就被改了。Java 里尤其要
new int[]{s, e}。另外 Python 的
intervals.sort() 是原地排序 —— 如果调用方不允许改输入顺序，先
sorted(intervals) 拷一份。
四、正确性：为什么"收段"之后那段永远定格
这是面试里真正值钱的一问。归纳论证：
- 初始：第一段成为当前合并区间，它罩住了已处理的全部区间；
- 每步 extend：新区间与当前区间重叠，
max 保证新的 curEnd 仍然罩住全部已处理区间；
- 每步 close：
s > curEnd 且排序保证后面的 start 更大 → 后面的区间和当前合并区间、以及它罩住的任何区间都不可能重叠 → 当前合并区间的边界不再受任何未来输入影响，可以定格收段。
这条不变量（"已处理区间永远被当前合并区间罩住"）也是状态机单测的核心断言。
五、复杂度
不排序有没有更快的？没有通用解 —— 区间合并本质上依赖"左端点有序"这个信息，它必须由比较排序（或按值域的桶/基数排序，若端点范围有限）给出。
六、Java 版
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
int curStart = intervals[0][0], curEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int s = intervals[i][0], e = intervals[i][1];
if (s <= curEnd) { // 端点相触也算重叠
curEnd = Math.max(curEnd, e); // 延伸取 max
} else {
result.add(new int[]{curStart, curEnd}); // 新造数组
curStart = s;
curEnd = e;
}
}
result.add(new int[]{curStart, curEnd});
return result.toArray(new int[0][]);
}
}
七、变体：一整族"排序 + 扫描"
家族共性：区间题先问一句"按哪个端点排序"—— 56 按
左端点（合并要罩住全部）、435/452 按
右端点（贪心留余地最大的）、986 干脆不排（输入已排）。排序键选对，剩下的都是线性扫描。
57 值得单独展开：它的输入
已经按左端点排好，所以连排序都省了，扫描时把"新区间"当作当前合并区间的初始值 —— 左边够不着的段直接收，碰到的就并进新区间，一旦够不着，右边剩下的原样接上。整个算法只有一次线性扫描：
def insert(intervals, new):
i, n = 0, len(intervals)
out = []
while i < n and intervals[i][1] < new[0]: # 左边：完全在新区间左侧
out.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= new[1]: # 中间：与新区间有重叠，并进来
new[0] = min(new[0], intervals[i][0])
new[1] = max(new[1], intervals[i][1])
i += 1
out.append(new)
while i < n: # 右边：原样接上
out.append(intervals[i]); i += 1
return out
对比 56 的流程会发现：
57 就是"排好序的 56 跳过排序、把第一段换成 new" —— 这也是为什么这两题在面试里经常连着出。
八、面试怎么答
- 先说排序：按左端点排序，O(n log n)，这一步买断了后面判断的合法性；
- 再说扫描：只和当前合并区间比一次 ——
s <= curEnd 延伸（取 max），否则收段新开；
- 主动补两句：端点相触算重叠（用
[1,4],[4,5] 自测）；结果要新造数组；
- 自测：
merge([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]] 且 merge([[1,4],[4,5]]) == [[1,5]]；
- 一句话总结：排序把"可能重叠的对"从 O(n²) 对压缩成"每个区间只比一次" —— 区间题的排序不是惯例，是算法本体。
系列上一篇：【LC 347】前 K 个高频元素。本文动画 7 帧，与状态机单测（23 例，与排序扫描 / 暴力连通分量两个独立参考解三向交叉验证）逐行核对过。