合并区间如何实现？（LeetCode 56）

简化版

给若干区间 intervals[i] = [start, end]，把所有重叠的区间合并，返回合并后的不重叠区间列表。做法：先按左端点升序排序，然后遍历，维护「当前合并段」的右边界；若下一个区间的左端点 <= 当前段右边界，就重叠 → 合并（右边界取两者 max）；否则不重叠 → 收尾当前段、把新区间作为新段开始。

详细版

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);   // 按左端点升序
    List<int[]> res = new ArrayList<>();
    for (int[] cur : intervals) {
        // 与最后一段不重叠：新开一段
        if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) {
            res.add(new int[]{cur[0], cur[1]});
        } else {
            // 重叠：合并，右端取较大者（cur 可能被上一段完全包住）
            int[] last = res.get(res.size() - 1);
            last[1] = Math.max(last[1], cur[1]);
        }
    }
    return res.toArray(new int[res.size()][]);
}

排序是前提：按左端点升序，保证区间「从左到右依次进场」。
合并判断：上一段右端 < 当前左端 → 不重叠；否则重叠。
右端取 max：合并时不能直接用 cur[1]，因为当前区间可能被上一段完全包含（如 [1,5] 吞掉 [2,3]）。
复杂度：排序 O(n log n) 主导，扫描 O(n)。

完整版教学

一、为什么必须先按左端点排序

不排序，区间乱序，判断哪些能合并要两两比较、O(n²) 还容易漏。按左端点升序排序后，区间就成了「起点从左往右」的有序流。这带来一个关键性质：当你处理到某个区间时，所有起点更靠左的区间都已处理完，你只需要拿它和「上一个已合并的段」比较——如果它和上一段都不重叠，那它和更早的段更不可能重叠（那些段的右端点只会更小或已被合并）。于是合并判断从「全局」降为「只看相邻」，一次扫描搞定。

二、合并的判定与执行

维护结果列表 res，其中最后一个元素是「当前正在生长的合并段」。对每个新区间 cur：

res 为空 或 上一段右端 < cur 左端：说明 cur 起点在上一段结束之后，两者不重叠 → 把 cur 作为新段加进 res。
否则（cur 左端 <= 上一段右端）：重叠 → 合并，令 上一段右端 = max(上一段右端, cur 右端)。

三、右端点为什么要取 max（关键易错点）

合并时很多人直接写 last[1] = cur[1]，这是错的。反例：上一段 [1,5]，当前 [2,3]。[2,3] 的左端 2 ≤ 5 判为重叠，但它完全被 [1,5] 包住，合并后仍应是 [1,5]。若直接赋 cur[1]=3，右端反而缩成 [1,3]，把 4、5 丢了——错。

所以必须 last[1] = max(last[1], cur[1])：区间可能是「延伸」（[1,5]+[3,8]→[1,8]），也可能是「被吞」（[1,5]+[2,3]→[1,5]），取 max 两种都对。

四、端点相接算不算重叠

[1,4] 和 [4,5] 要不要合并？取决于题意。LeetCode 56 认为端点相接也要合并（合成 [1,5]），所以判断用 上一段右端 < cur 左端 才算「不重叠」（严格小于）。若某题规定「相接不算重叠」，则改成 <=。这个 < 与 <= 的取舍是区间题最常见的边界坑，做题前先确认定义。

五、完整走一遍

[[1,3],[2,6],[8,10],[15,18]]：

排序后不变（左端已升序）。
[1,3] 入 res：res=[[1,3]]。
[2,6]：2 <= 3 重叠 → 合并，右端 max(3,6)=6：res=[[1,6]]。
[8,10]：6 < 8 不重叠 → 新段：res=[[1,6],[8,10]]。
[15,18]：10 < 15 不重叠 → 新段：res=[[1,6],[8,10],[15,18]]。

结果 [[1,6],[8,10],[15,18]]。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：按左端升序后，当前区间只可能与结果最后一段合并；重叠时右端更新为 max。

闭区间常用 `next.start≤cur.end`；若不重叠先输出 cur 并开启新区间

数字推演：[1,4],[2,3] 必须合成 [1,4]，若直接把右端写成3会错误缩短。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：空输入、端点相接语义和排序比较器溢出都需处理。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：按左端升序后，当前区间只可能与结果最后一段合并；重叠时右端更新为 max。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“[1,4],[2,3] 必须合成 [1,4]，若直接把右端写成3会错误缩短”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：空输入、端点相接语义和排序比较器溢出都需处理。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：重叠时右端直接取 next.end。 嵌套区间会错误缩短，应取 max。
误区：不排序也能一次扫描。 潜在重叠段不会相邻，无法局部判断。
误区：合并后应保留两个原区间。 输出应替换为覆盖二者的单一区间。
追问：为什么只看结果最后一段？ 左端有序使更早已结束区间不可能与当前重新相交。
追问：端点相接如何处理？ 按题目开闭语义选择 ≤ 或 <。
追问：复杂度是多少？ 排序 O(n log n)，扫描 O(n)。

九、加强记忆

合并区间 = 按左端点升序排序 + 一次扫描合并。维护「当前合并段」，新区间左端 > 上一段右端才算不重叠（新开一段），否则重叠 → 合并，且右端必须 max(last[1], cur[1])（防止当前区间被上一段完全包住时右端缩水）。排序让「判重叠」从全局降为「只比上一段」。端点相接算不算重叠决定用 < 还是 <=。O(n log n)。核心两个坑：排序别忘、右端取 max。

简化版

详细版