如果你在力扣上刷题刷到数组/区间这个专题大概率会和合并区间这道题打个照面。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 pairint, int PII; void merge(vectorPII segs) { sort(segs.begin(), segs.end()); // pair 默认先 first 后 second 升序 vectorPII 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输入从 vectorpairint,int 变成了二维数组模板骨架完全不变变的只是排序写法和边界初始化方式。所以你可以把这道题理解成同一套核心套路在两个平台上的两种皮相。能背下这套骨架力扣 56、ACwing 803 其实就都拿下了。2.2 起点排序和终点排序怎么选合并区间用起点排序这是定了的。原因很简单你要从左端点最小的区间开始“滚雪球”起点的顺序决定了扫描过程是单向推进的。如果改成按终点排序你拿到第一个区间时根本不知道全局最左边的区间是谁合并范围随时可能向左扩张只能反复调整结果复杂度就退化回 O(n^2) 甚至更糟。但并不是所有区间题都按起点排序这里我把常见的几道题放在一张表里方便对照典型题目排序方式贪心维护的关键变量力扣 56 合并区间按起点升序当前合并区间的右端点最大值力扣 435 无重叠区间按终点升序上一个被保留区间的右端点力扣 452 用最少数量的箭引爆气球按起点升序公共交集区间的右端点最小值力扣 1288 删除被覆盖区间起点升序、终点降序当前已覆盖的最远右端点看出来了吗排序方向取决于你想要什么顺序的“局部最优”合并区间需要从前往后构建连续块所以起点升序无重叠区间希望尽早结束当前区间以容纳更多答案所以终点升序气球问题希望公共交集尽量向右扩展所以起点升序但维护的是右端点最小值。这道题的排序选择不是拍脑袋而是贪心方向决定的。理解这一点后面试官把题目稍微变形你也能很快定出排序策略。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(keylambda x: x[0]) 一行搞定Java 里 Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]))。这里有个隐形的知识C 的 sort 对 vectorvector 也是按字典序排序的所以力扣 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])); Listint[] 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不用减法。第三是循环从 i1 开始因为第 0 个区间已经承担了 curStart 和 curEnd 的初始化工作。第四是循环结束后必须再执行一次 merged.add把最后一组当前区间推进结果这一行忘掉就会出现经典的“少一个区间”错误我在第四部分还会专门讲。最后返回用的是 toArray(new int[merged.size()][])这个写法是二维 List 转数组的标准姿势size 传进去可以让 Java 分配正确大小的数组避免扩容时的反射开销。面试场景下Java 是这么写的就基本满意了。如果你还想再稳一点可以把 intervals.length 1 的判断拿掉让循环从 i0 开始把逻辑改成先判断 merged 是否为空但那种写法在简洁度上不如现在这版。3.2 Python实现刷题最快def merge(intervals): intervals.sort(keylambda 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 mergedPython 版是我私下刷题最常用的一版因为它可以直接原地修改 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: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); // 默认字典序排序 vectorvectorint 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()) 对 vectorvector 的作用是按外层数组的字典序排序也就是先比第一个数再比第二个数。这个特性和 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 小于 bb 小于 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建议把这道题放在排序专题的第一个去啃啃透它后面一串区间题都会顺很多。别小看这种基础模板题它才是真正能让你在面试里稳定拿分的底子。
合并区间模板精讲：排序+贪心，从LeetCode 56到区间家族
如果你在力扣上刷题刷到数组/区间这个专题大概率会和合并区间这道题打个照面。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 pairint, int PII; void merge(vectorPII segs) { sort(segs.begin(), segs.end()); // pair 默认先 first 后 second 升序 vectorPII 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输入从 vectorpairint,int 变成了二维数组模板骨架完全不变变的只是排序写法和边界初始化方式。所以你可以把这道题理解成同一套核心套路在两个平台上的两种皮相。能背下这套骨架力扣 56、ACwing 803 其实就都拿下了。2.2 起点排序和终点排序怎么选合并区间用起点排序这是定了的。原因很简单你要从左端点最小的区间开始“滚雪球”起点的顺序决定了扫描过程是单向推进的。如果改成按终点排序你拿到第一个区间时根本不知道全局最左边的区间是谁合并范围随时可能向左扩张只能反复调整结果复杂度就退化回 O(n^2) 甚至更糟。但并不是所有区间题都按起点排序这里我把常见的几道题放在一张表里方便对照典型题目排序方式贪心维护的关键变量力扣 56 合并区间按起点升序当前合并区间的右端点最大值力扣 435 无重叠区间按终点升序上一个被保留区间的右端点力扣 452 用最少数量的箭引爆气球按起点升序公共交集区间的右端点最小值力扣 1288 删除被覆盖区间起点升序、终点降序当前已覆盖的最远右端点看出来了吗排序方向取决于你想要什么顺序的“局部最优”合并区间需要从前往后构建连续块所以起点升序无重叠区间希望尽早结束当前区间以容纳更多答案所以终点升序气球问题希望公共交集尽量向右扩展所以起点升序但维护的是右端点最小值。这道题的排序选择不是拍脑袋而是贪心方向决定的。理解这一点后面试官把题目稍微变形你也能很快定出排序策略。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(keylambda x: x[0]) 一行搞定Java 里 Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]))。这里有个隐形的知识C 的 sort 对 vectorvector 也是按字典序排序的所以力扣 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])); Listint[] 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不用减法。第三是循环从 i1 开始因为第 0 个区间已经承担了 curStart 和 curEnd 的初始化工作。第四是循环结束后必须再执行一次 merged.add把最后一组当前区间推进结果这一行忘掉就会出现经典的“少一个区间”错误我在第四部分还会专门讲。最后返回用的是 toArray(new int[merged.size()][])这个写法是二维 List 转数组的标准姿势size 传进去可以让 Java 分配正确大小的数组避免扩容时的反射开销。面试场景下Java 是这么写的就基本满意了。如果你还想再稳一点可以把 intervals.length 1 的判断拿掉让循环从 i0 开始把逻辑改成先判断 merged 是否为空但那种写法在简洁度上不如现在这版。3.2 Python实现刷题最快def merge(intervals): intervals.sort(keylambda 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 mergedPython 版是我私下刷题最常用的一版因为它可以直接原地修改 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: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); // 默认字典序排序 vectorvectorint 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()) 对 vectorvector 的作用是按外层数组的字典序排序也就是先比第一个数再比第二个数。这个特性和 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 小于 bb 小于 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建议把这道题放在排序专题的第一个去啃啃透它后面一串区间题都会顺很多。别小看这种基础模板题它才是真正能让你在面试里稳定拿分的底子。