如果你在力扣上刷题刷到数组/区间这个专题，大概率会和合并区间这道题打个照面。LeetCode 56. Merge Intervals 是面试里的老熟人，在ACwing的算法基础课里它又叫“区间合并”模板题，几乎是排序专题开篇就练的骨架级题目。我第一次把它当模板背下来的时候，觉得排序加扫描这个思路理所当然；等自己真上手写，才发现里面门道不少：比较器怎么写、最后一个区间为什么总丢、碰到 [1,5] 和 [2,3] 这种包含关系时为什么必须取 max 而不是直接覆盖。这篇文章我就把这题从题目拆解到三种语言实现，再到几个容易踩的坑和它的变形题，一次讲清楚。适合准备校招面试、刷竞赛模板，或者想把区间类题目彻底搞利索的同学。

1. 题目拆解：合并区间到底在考什么

1.1 一眼识别题目特征

题目输入是一组区间，形如 intervals[i] = [start_i, end_i]，要求把所有有重叠的区间合并，输出一个新的区间数组。力扣原题给的那个例子最有代表性：intervals = [[1,3],[2,6],[8,10],[15,18]]，输出 [[1,6],[8,10],[15,18]]。因为 [1,3] 和 [2,6] 在 2 和 3 之间重叠，合并成 [1,6]，其他两个区间和它俩隔开了，保持原样。看到这种描述，第一反应就应该是：排序题、贪心题、区间扫描题。

还有一个特征容易被忽视：输入顺序完全是乱的，没有任何规律。换句话说，出题人不会好心帮你把区间按起点排好。如果你拿到题目后第一反应是“那我遍历数组，拿每个区间和后面的区间两两比较”，这就是典型的直觉错误，后面我会解释为什么这种暴力做法在遇到链式合并时会非常麻烦。另一个重要特征是区间端点值范围，力扣 56 里 start_i 和 end_i 都在 -10^4 到 10^4 之间，区间数量最多 10^4 个。这个数据规模意味着 O(n log n) 的排序解法是标准答案，也意味着你完全可以先花 O(n log n) 做排序，再做 O(n) 扫描，整体依然是一个能稳过的解法。

1.2 为什么排序是这道题的命门

我先模拟一下不排序的暴力法会撞到什么。假设你已经往结果列表里放了一个 [1,5]，现在来了个 [2,3]，它被 [1,5] 包含，合并结果还是 [1,5]；接着又来了个 [4,6]，它跟 [1,5] 相交，于是结果变成 [1,6]；此时如果之前还有个 [3,4] 没处理，它其实早就被包进去了。问题在于：区间之间的重叠关系是“链式传播”的，你不排序就无法预知哪个区间会触发下一轮合并，处理顺序稍有不同，结果列表就在不断被改写。在这种状态下要做到一遍扫描完美合并，基本要靠维护有序结构，代价不比排序低。

把区间按起点升序排好之后，整个问题一下子变单纯了。因为左端点单调不减，任何一个新区间都只会出现在当前合并区间的“右方或内部”，不会再跑回前面去纠缠已合并完的区间。此时你只需要干一件事：维护一个“当前正在合并的区间”，用 curStart 记左端点，curEnd 记右端点。每次遇到新区间，如果它的左端点还在 curEnd 的覆盖范围内，说明和当前区间重叠或相接，那就把 curEnd 更新成两者的最大值；如果它的左端点已经越过了 curEnd，说明从 curStart 开始的那段合并彻底结束了，把它存进结果列表，再拿当前区间作为新的合并起点。整个过程从左到右扫一遍，不回溯，中间结果也不会被后续区间推翻。

用生活里的例子理解更直观。想象你有一堆日程安排，把每段日程按开始时间排好队。然后从头往后看：如果下一条日程的开始时间早于等于当前这段合并日程的结束时间，就把这段合并日程的结束时间往后推到更晚的那个；如果下一条日程的开始时间已经比当前合并日程的结束时间还晚，说明中间有空档，这个合并日程可以定稿了。你从头扫到尾，所有日程就自然被分成了连续的大块。

1.3 贪心合并的循环不变量

不少同学觉得看懂样例就够了，但面试时被追问“为什么这个贪心是对的”就容易卡壳。这里我可以提供一个很顺的口径，也是算法圈子常说的循环不变量：扫描到第 i 个区间时，如果当前合并区间存在，那么它表示“从 curStart 开始，所有能连到 curEnd 的区间的最大右端点”；结果列表里已经保存的所有合并区间，任意两个都不重叠，且已经是最终答案的前缀。这个性质在每次迭代后都保持：要么把新区间并进当前区间，curEnd 变为更新后的最大值，性质依然成立；要么把当前区间定稿并开启新的当前区间，性质依然成立。循环结束后，再把最后一个当前区间定稿，所有区间就被完整、无重叠地合并完毕。

这也解释了为什么合并时要写 curEnd = max(curEnd, intervals[i][1])，而不是直接 curEnd = intervals[i][1]。因为新区间可能完全被当前区间包含，比如当前区间是 [1,5]，新来的是 [2,3]，如果直接覆盖，右端点从 5 变成 3，等于把人家的合并范围往回缩了，后面的区间再拿 3 去比较，结果必错。max 这一步看似不起眼，实际上是整个贪心正确性的地基。

2. 排序选型：为什么ACwing里一行sort就够了

2.1 ACwing模板里的区间合并骨架

标题里特意写了“ACwing模板题（排序）”，说明这道题在竞赛语境里是拿来当模板背的。ACwing 803 区间合并的经典做法是这样写的：

#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; void merge(vector<PII>& segs) { sort(segs.begin(), segs.end()); // pair 默认先 first 后 second 升序 vector<PII> res; int st = -2e9, ed = -2e9; // 哨兵区间 for (auto& seg : segs) { if (ed < seg.first) { // 注意是 < 而不是 <= if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else { ed = max(ed, seg.second); } } if (st != -2e9) res.push_back({st, ed}); }

这段模板有两个值得留意的设计。第一个是 pair 排序：C++ 的 sort 对 pair 默认按字典序，先比较 first，再比较 second，所以区间天然按起点升序、起点相同时按终点升序排列，连自定义比较器都不用写。第二个是哨兵值 -2e9：因为区间值域不会低到 -2e9，把初始区间的 st、ed 设成一个绝对不存在的区间，就能让第一个区间的处理也走同一个 if-else 分支，最后再用 st != -2e9 判断到底有没有处理过任何区间。这种哨兵写法在竞赛里很常见，好处是逻辑统一，坏处是代码里多了一个魔法值，阅读时需要习惯。

到了力扣 56，输入从 vector<pair<int,int>> 变成了二维数组，模板骨架完全不变，变的只是排序写法和边界初始化方式。所以你可以把这道题理解成同一套核心套路，在两个平台上的两种皮相。能背下这套骨架，力扣 56、ACwing 803 其实就都拿下了。

2.2 起点排序和终点排序怎么选

合并区间用起点排序，这是定了的。原因很简单：你要从左端点最小的区间开始“滚雪球”，起点的顺序决定了扫描过程是单向推进的。如果改成按终点排序，你拿到第一个区间时根本不知道全局最左边的区间是谁，合并范围随时可能向左扩张，只能反复调整结果，复杂度就退化回 O(n^2) 甚至更糟。

但并不是所有区间题都按起点排序，这里我把常见的几道题放在一张表里，方便对照：

看出来了吗？排序方向取决于你想要什么顺序的“局部最优”：合并区间需要从前往后构建连续块，所以起点升序；无重叠区间希望尽早结束当前区间以容纳更多答案，所以终点升序；气球问题希望公共交集尽量向右扩展，所以起点升序但维护的是右端点最小值。这道题的排序选择不是拍脑袋，而是贪心方向决定的。理解这一点后，面试官把题目稍微变形，你也能很快定出排序策略。

2.3 写排序比较器的三条铁律

力扣 56 在 Java 里要自己写比较器，这里我踩过几次坑，直接提炼成三条经验。第一条：别用差值写法 (a, b) -> a[0] - b[0]。这种写法在力扣 56 里可能不会出大问题，因为端点值只有 -10^4 到 10^4，但如果你把它带到别的题，比如坐标是 2^31 级别的区间，a[0] - b[0] 可能溢出，导致排序结果完全错乱，更致命的是这会破坏比较器的传递性。Java 的 TimSort 一旦检测到“a 应该排在 b 前，b 应该排在 c 前，但 a 又比 c 小或等于”这种矛盾，会直接抛异常。稳妥写法是 Integer.compare(a[0], b[0])。

第二条：如果考点允许，优先用语言自带的能力。C++ 里 sort 对 pair 默认排序就是想要的；Python 里 intervals.sort(key=lambda x: x[0]) 一行搞定；Java 里 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]))。这里有个隐形的知识：C++ 的 sort 对 vector<vector > 也是按字典序排序的，所以力扣 56 的 C++ 解法甚至可以不写比较器，默认 sort(intervals.begin(), intervals.end()) 就能用。

第三条：比较器只比较必要的维度。合并区间时第二维要不要排？不需要。因为扫描合并用的是 max，终点顺序对结果没有任何影响；写多了反而让比较器复杂，增加出错概率。但如果你在写 1288 删除被覆盖区间那种题，就一定要起点升序、终点降序，不能反过来，我后面会讲到。

3. 三种语言完整实现与逐行剖析

3.1 Java实现：面试首选

力扣上最主流的写法是：

class Solution { public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length <= 1) { return intervals; } Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); int curStart = intervals[0][0]; int curEnd = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= curEnd) { curEnd = Math.max(curEnd, intervals[i][1]); } else { merged.add(new int[]{curStart, curEnd}); curStart = intervals[i][0]; curEnd = intervals[i][1]; } } merged.add(new int[]{curStart, curEnd}); return merged.toArray(new int[merged.size()][]); } }

这段代码有四个落点要注意。第一是判空和长度小于等于 1 的快速返回，除了避免空指针，还能少想一个边界分支。第二是排序后一定用 Integer.compare，不用减法。第三是循环从 i=1 开始，因为第 0 个区间已经承担了 curStart 和 curEnd 的初始化工作。第四是循环结束后必须再执行一次 merged.add，把最后一组当前区间推进结果；这一行忘掉就会出现经典的“少一个区间”错误，我在第四部分还会专门讲。最后返回用的是 toArray(new int[merged.size()][])，这个写法是二维 List 转数组的标准姿势，size 传进去可以让 Java 分配正确大小的数组，避免扩容时的反射开销。

面试场景下，Java 是这么写的就基本满意了。如果你还想再稳一点，可以把 intervals.length <= 1 的判断拿掉，让循环从 i=0 开始，把逻辑改成先判断 merged 是否为空；但那种写法在简洁度上不如现在这版。

3.2 Python实现：刷题最快

def merge(intervals): intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: merged[-1][1] = max(merged[-1][1], interval[1]) return merged

Python 版是我私下刷题最常用的一版，因为它可以直接原地修改 merged 列表里最后一个区间的右端点。关键判断同样要搞清楚：merged[-1][1] < interval[0] 表示“当前区间和结果列表最后一个区间没有重叠”，注意这里用的是小于而不是小于等于，因为力扣 56 认为端点相接也算重叠，需要合并；如果你把小于改成小于等于，[1,2] 和 [2,3] 就会错误地变成两个区间。

很多人写 Python 版容易犯一个错误：更新时写成 merged[-1][1] = interval[1]，忘了取 max。比如 merged[-1] 是 [1,5]，interval 是 [2,3]，更新后右端点变成 3，后面再拿 3 去和 [4,6] 比较，会以为中间有空档，结果错得离谱。所以哪怕在 Python 这种“看起来为所欲为”的语言里，也要老老实实写 max。

3.3 C++实现：ACwing风格

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); // 默认字典序排序 vector<vector<int>> res; int st = intervals[0][0], ed = intervals[0][1]; for (int i = 1; i < intervals.size(); i++) { if (intervals[i][0] <= ed) { ed = max(ed, intervals[i][1]); } else { res.push_back({st, ed}); st = intervals[i][0]; ed = intervals[i][1]; } } res.push_back({st, ed}); return res; } };

在这个版本里，sort(intervals.begin(), intervals.end()) 对 vector<vector > 的作用是按外层数组的字典序排序，也就是先比第一个数，再比第二个数。这个特性和 pair 排序其实是一回事，所以 C++ 解法一行比较器都不用写，比 Java 干净不少。如果你是从 ACwing 模板转过来看这道题的，会发现这段代码和模板的区别主要在于：模板用 Pair 和哨兵值，这里用二维 vector 和第一个区间初始化。核心的 if (intervals[i][0] <= ed) 和 ed = max(ed, intervals[i][1]) 完全一致。

还有第三种更贴近 ACwing 原模板的写法：不判空，直接初始化 st = -2e9, ed = -2e9，循环所有区间，最后再用哨兵判断。这种写法能写出统一的循环结构，面试时可以提一嘴“我还有个竞赛模板的写法”，但如果你现场手写，我还是建议用第一个区间初始化的版本，分支更少，不容易写错。

3.4 边界条件与复杂度核算

把三种语言的实现放在一起看，边界条件的处理其实是同一套：空输入直接返回空；单个区间直接返回；所有区间重叠时只输出一个区间；不在同一块时按顺序输出多个区间。还有一个容易被忽略的边界是端点相接，比如 [1,2] 和 [2,3]，力扣 56 是能合并成 [1,3] 的，所以判断条件必须用 <= ed，而不是 < ed。如果你在别的题里见到“严格重叠”的说法，那时才改成 <。

复杂度这块很明确：排序 O(n log n)，一趟扫描 O(n)，总时间复杂度 O(n log n)。空间上，如果不把输出数组算进去，每个实现只需要常数个保存 curStart、curEnd 的变量，算是 O(1) 辅助空间；但要注意 Java 的 Arrays.sort 对对象数组使用 TimSort，实际会申请 O(n) 的临时数组，严格算法分析里这可能算 O(n) 空间。竞赛和力扣通常只看你递推时的额外变量，所以说不算输出的 O(1) 辅助空间也能接受。面试被问到时，最好主动说清楚“我看作 O(log n) 是排序递归栈，严格一点是 O(n)”，表示你想过这层，比光背一个 O(1) 要加分。

4. 现场踩坑实录与排查技巧

4.1 比较器违约异常

我第一次用 (a, b) -> a[0] - b[0] 跑一个坐标很大的区间题时，sort 直接抛了“Comparison method violates its general contract!”异常，当时人都是懵的。后来才明白，Java 的 TimSort 要求比较器满足严格全序，也就是自反、反对称、传递三样都要有。如果用减法比较，一旦 a[0] 和 b[0] 逼近 int 的边界，a[0] - b[0] 溢出成负数，就会产生“a 小于 b，b 小于 c，但 a 大于 c”这种矛盾，排序算法没法再继续。解法非常简单：Integer.compare(a[0], b[0])。它内部实现是 (x < y) ? -1 : (x == y ? 0 : 1)，不会溢出，且天然满足传递性。

不只这道题，以后所有需要自定义比较器的题都建议默认使用 Integer.compare 或 Long.compare。这个习惯养成了，基本能避开一大类诡异的排序 bug。

4.2 最后一个区间总被漏掉

“少一个区间”是合并区间最常见的高频 bug。原因是这样的：扫描循环里，每当遇到一个与当前区间断开的区间，你就把当前的 [curStart, curEnd] 存进结果，然后开启新的一段。循环结束后，最后一个当前区间还没被存，必须手动补一次 merged.add({curStart, curEnd})。很多人写着写着就忘了这一行，输出结果永远差一块。

怎么避免？两个办法。第一，把“提交当前区间”的代码抽成一个 add 操作，调试时在纸上标一个“循环结束后还要 add 一次”的钩子。第二，改用 ACwing 哨兵写法，用 st != -2e9 判断是否有待提交的区间，循环统一处理后再补一次判断，从结构上消灭遗漏。无论哪种，核心是记住：这个题一定会在循环外收尾。

4.3 更新右端点时直接覆盖

我见过不止一次这种写法：

if (intervals[i][0] <= curEnd) { curEnd = intervals[i][1]; }

问题我已经在前面说过了。当新区间被当前区间完全包含时，比如当前 [1,5]，新来 [2,3]，直接覆盖会把 curEnd 从 5 改成 3，把合并范围回缩。更隐蔽的是，如果后面接着一个 [3,4]，用 3 去判断 [3,4] 会被误判为不重叠或重叠的分界，结果不稳定。这是一个典型的“单测数据恰好过了，但逻辑却错了”的代码。写成 Math.max(curEnd, intervals[i][1]) 后，这个场景就稳了。排查这个问题的方法也简单：自己造几个包含关系的用例，比如 [[1,5],[2,3],[3,4]]，跑一遍看输出。

4.4 重叠判断的边界语义

“<= 还是 <”这个一算子之差，能直接改变答案。力扣 56 里 [1,2] 和 [2,3] 要合并，所以不重叠判断应该是 merged[-1][1] < interval[0]，重叠判断就是 interval[0] <= curEnd。如果你写成 < curEnd，就会把这种端点相接的区间拆开，少合并一对；如果你在追击问题时遇到“用最少的箭引爆气球”这种题，端点相接的气球又算能被同一支箭引爆，判断逻辑仍然是相交时用 <=。反过来，有些变体题定义“区间重叠”为真正的交集长度大于 0，端点相接不算，那就要用 < 判重叠。所以做题前第一件事是确认题目的重叠定义，别想当然。

注意：如果你不确定题目里的“重叠”到底算不算端点相接，先看输入输出示例。力扣 56 示例里 [1,3] 和 [2,6] 合并是因为有交集，但真正暴露端点合并语义的用例是 [[1,2],[2,3]]，输出应该只有一个 [1,3]。写代码前自己先跑一遍这个用例。

5. 从模板题延伸：一网打尽区间家族

5.1 力扣57 插入区间

力扣 57 给的是一个已经有序且无重叠的区间列表，让你插入一个新的区间。最简单的做法就是复用 56 的模板：把 newInterval 加进 intervals，排序后调用 merge，一句话结束。这种解法在面试里能过，但你要是真想练好区间题，最好还是写 O(n) 的三段式。思路是分三块处理：newInterval 左边的、和 newInterval 相交的、newInterval 右边的。左边那些区间的右端点严格小于 newInterval 的左边界，直接加入结果；所有与 newInterval 相交的区间，把 newInterval 的左端点和右端点分别取 min 和 max 延展；剩下的右边区间原样追加。三步完事，无需求数组。我自己刷题时对这题的建议是：先用 merge 模板拿分，再手写一遍三段式加深理解，两种做法都练。

5.2 力扣452 用最少数量的箭引爆气球

452 题是合并区间非常好的对照题。每个气球的直径用一个区间表示，一支箭扎在某个 x 坐标上，所有包含这个 x 的区间都会爆。目标是用最少的箭，也就是找最少的位置，覆盖所有区间。排序后，维护的不是右端点最大值，而是当前这组可一起引爆的气球的公共右端点最小值。当新区间的起点大于当前公共右端点时，说明前面这组必须单独射一支箭了，计数加一，然后用新区间开启新的一组。这个贪心里“公共区间必须非空”和合并区间“只要碰头就能合并”是同一个判定系统的两个方向，把 56 练透了，452 的代码看一眼模板就能写。

5.3 力扣435 无重叠区间与1288 删除被覆盖区间

435 题要求移除最少的区间，使得剩下的区间互不重叠。经典贪心是按终点升序排序，然后尽可能多地保留区间：维护上一个被保留区间的右端点，遇到新区间起点大于等于它时保留，否则丢弃。这个排序选择正好和 56 相反，因为这里要的是“尽快结束当前区间，给后面留空间”。1288 题则要你删除所有被其他区间覆盖的区间。排序要写成起点升序、终点降序：起点相同让较大的区间排在前面，这样扫描时一旦发现当前区间的右端点小于等于已经覆盖过的最远右端点，它一定是被覆盖的，可以删除。这四道题算下来，你会发现核心都是“排序确定贪心方向，扫描维护一个关键区间”的模板，区别只在维护的是最大值还是最小值、排序用的是起点还是终点。把 56 吃透，等于拿到了整个区间家族的钥匙。

我个人刷这类模板题的习惯是：第一遍看着模板默写，第二遍完全合上代码手写，第三遍换一种语言再写一遍。三遍下来，合并区间这个套路基本就长在脑子里了，后来面试遇到类似的题，我甚至会先跟面试官说一句“这道题考排序，我先按左端点排序，再用两个变量维护当前合并区间，最后循环外补一次提交”，对方通常都会点头。如果你也在准备力扣热题 100，建议把这道题放在排序专题的第一个去啃，啃透它，后面一串区间题都会顺很多。别小看这种基础模板题，它才是真正能让你在面试里稳定拿分的底子。