“合并区间”这道题，基本是算法手撕环节里的老朋友了。我最近不止一次被问到：为什么思路明明很简单，真到了要“快手手撕”的时候，却总是写不干净？要么漏了排序，要么合并时右边界取错，要么一上来就踩了空输入的空指针。所谓“快手手撕”，说的就是在有限时间里把这道题完整、正确、有说服力地手写出来，而不是背个模板交差。这篇文章我打算把合并区间这个题彻底拆开讲清楚，从最朴素的直觉出发，到代码实现、边界条件、复杂度分析，再到面试现场该怎么表现，全程用我实际复盘时的思路来写。不管你是刚开始刷题的新手，还是已经刷过几百题准备冲刺的老手，只要想把手撕合并区间做成稳定拿分的项目，这篇都值得你花十分钟看完。
1. 这道题为什么值得专门拆解：题目还原与考察点透视
1.1 先把题面说清楚，防止“假会做”
合并区间的标准描述其实非常短：给你一个二维数组，里面每个元素都是长度为 2 的子数组，例如intervals[i][0]表示区间左端点，intervals[i][1]表示区间右端点，请你把所有重叠区间合并成一个更大的区间，并返回合并后的新列表。
比如：
输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]为什么输出是这样？因为[1,3]和[2,6]存在公共部分[2,3]，合并后变成[1,6]；而[8,10]、[15,18]与前面合并结果都不重叠，所以原样保留。
这题第一眼看过去，很多人觉得“不就是比大小吗”。但实际动手写的时候，会发现三个问题集中爆发：要不要先排序？合并时右边界应该怎么更新？两个区间紧挨着算不算重叠？这三个问题没有一个能在“看懂答案”的阶段被真正解决，必须自己亲手推导一遍。所以我不建议你直接背代码，先把下面的推导读懂，比默写十遍都管用。
1.2 面试官爱考它的真实原因：一题考五件事
我复盘过不少同类区间问题，发现合并区间几乎承担了算法面试里最典型的一类考察模型：排序预处理 + 线性贪心扫描 + 边界防御。具体拆开来看，它至少同时考察了五个点：
- 排序能力：需要理解为什么排序能让合并决策从“两两比较”降维成“单向扫描”。
- 贪心思想：每一步只需要和已合并区间序列的最后一个做比较，局部最优直接得到全局最优。
- 边界意识：空数组、单元素数组、区间完全包含、紧邻区间、未排序输入，每一种都要正确处理。
- 复杂度的直觉：知道排序是 O(n log n)，扫描是 O(n)，整体是 O(n log n)，并且能说清楚为什么不可能比这更优。
- 迁移能力：这个题的变形非常多，插入区间、求重叠区间数量、会议安排都基于同一套思维。
换句话说，面试官选这道题，不是看你知不知道答案，而是想看你怎么从零到一把它写出来。搞懂这里面的“为什么”，比记住“怎么写”重要得多。
2. 手撕之前的三分钟：从直觉到贪心策略的完整推导
2.1 任意两个区间之间，只存在四种关系
在写任何代码之前，咱先把两个区间[a1, a2]和[b1, b2]（假设a1 <= b1）之间的关系列干净。区间问题的核心，说白了就是对这几种关系的分类讨论：
| 关系 | 条件 | 合并结果 | 示例 |
|---|---|---|---|
| 完全分离 | a2 < b1 | 保持两个区间不变 | [1,2]与[3,4] |
| 部分重叠 | a2 >= b1且a2 < b2 | [a1, b2] | [1,3]与[2,5] |
| 包含关系 | a2 >= b2 | [a1, a2] | [1,10]与[2,5] |
| 紧邻关系 | a2 == b1 | 按题目约定，通常视为可合并 | [1,2]与[2,3]合并为[1,3] |
注意我这里的假设是左边的区间起点更小。如果输入没有排序，一定会出现右区间起点反而更小的情况，这也是为什么排序几乎无法跳过。紧邻关系的处理尤其容易被忽略：大多数区间合并问题里，[1,2]和[2,3]会被认为覆盖了完整的[1,3]。但如果题目明确说了区间是离散整数点，那就要额外确认；好在 LeetCode 原题和绝大多数面试版都采用连续区间语义，紧邻边界直接合并。
2.2 排序到底帮忙做了什么：把二维比较降成一维扫描
如果输入是完全乱序的，比如[[2,6],[8,10],[1,3],[15,18]]，你虽然有四个区间，但不能保证第一个区间就是全局最左边的。这种情况下，你没法确定“当前区间应该和谁比”，每次都可能需要回头看之前所有区间，最坏情况复杂度会变成 O(n²)。
一旦所有区间按左端点升序排列，事情就变得很舒服：从左往右扫描时，当前区间的左端点一定大于等于已经扫描过的所有区间左端点。因此，是否发生重叠，只需要看当前区间的左端点interval[0]和“合并结果序列里最后一个区间的右端点”last[1]的关系。前面那些区间不用再管了，它们不可能和当前区间产生新的交叉关系。这就是一个非常典型的贪心策略：每一步基于当前局部信息做出合并或不合并的决定，因为排序保证了以后不会出现需要回退的情况。
2.3 合并条件用代码逻辑怎么写：判断与更新的关键
推导到这里，核心逻辑其实只剩下两句话：
- 如果当前区间左端点大于结果序列最后区间的右端点，说明没有交集，直接把当前区间追加进结果。
- 否则说明有交集，需要合并。合并后右边界取“结果序列最后区间的右端点”和“当前区间右端点”的较大值，左边界保持不变（因为已经按左端点排过序，且当前左端点不可能小于最后一个区间的左端点）。
为什么右边界一定要取较大值？因为区间可能存在“包含”关系。比如结果里最后是[1,10]，当前是[2,5]，如果直接取当前区间右端点5，就会发现合并后变成[1,5]，把原来的右边界10搞丢了。这是新手手撕时最典型的错误之一。
3. 代码实现：从第一版到能直接交差的完整版本
3.1 Python 参考实现与逐行注释
下面这个版本是我认为最干净、最适合手撕的 Python 写法，不搞花活，核心逻辑一目了然：
def merge(intervals): # 处理空输入，避免后面访问 res[-1] 出错 if not intervals: return [] # 按区间左端点升序排序 intervals.sort(key=lambda x: x[0]) # 结果列表 res = [] for interval in intervals: # 如果结果为空，或者当前区间与最后一个结果区间不重叠 if not res or interval[0] > res[-1][1]: res.append(interval) else: # 有重叠，右边界取较大值 res[-1][1] = max(res[-1][1], interval[1]) return res这段代码的巧妙之处在于res[-1]永远是当前扫描进度下“待合并区间”的临时存储点。每次遇到重叠，就直接修改它；遇到不重叠，就开启一个新区间。整个过程只需要一次遍历，没有嵌套循环。
需要注意的一个细节是：intervals.sort(key=lambda x: x[0])是对原列表原地排序。在很多手撕场景里，面试官可能会问“能不能不修改原数组”，如果在意这一点，可以用sorted(intervals, key=lambda x: x[0])生成新列表，代价是额外 O(n) 空间。
3.2 换个语言手撕时的关键差异
Python 写习惯了，换到别的语言时容易忽略几个差异点，我在这里统一说一下。
Java：常用List<int[]>作为数据结构，排序用list.sort((a, b) -> a[0] - b[0])。注意 lambda 里减法可能溢出，面试时一般数据量不会触发，但严谨写法应该用Integer.compare(a[0], b[0])。最终返回时用res.toArray(new int[res.size()][])，这个转换语法本身也经常是一个小的考点。
Go：排序可以用sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })。切片处理上，res = append(res, interval)与res[len(res)-1][1] = ...都是常规操作。要注意切片共享底层的坑：如果你把interval直接 append 进res，并且后续又修改了res[-1][1]，由于指向同一个底层数组，原切片也会被改动。在这个题目里没有影响，但性格上还是建议遇到重叠时创建一个新切片[]int{prev[0], max(prev[1], interval[1])}再放进去，语义更安全。
C++：排序用sort(intervals.begin(), intervals.end())，因为vector<int>默认按字典序比较，正好先比左端点再比右端点，符合需求。合并时可以通过res.back()取最后一个区间。
3.3 内存优化：原地覆盖的玩法
有些追求极致性能的人会问：能不能不使用额外的res列表？是可以的，思路是利用原数组空间，维护一个写入指针：
def merge_inplace(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) count = 0 for interval in intervals: if count == 0 or interval[0] > intervals[count - 1][1]: intervals[count] = interval count += 1 else: intervals[count - 1][1] = max(intervals[count - 1][1], interval[1]) return intervals[:count]这个方案的空间复杂度是 O(1)（不考虑排序栈空间），但会修改原数组。我个人的建议是：面试时不要主动秀这个方案，除非被问到空间优化。因为原地覆盖的写法会降低可读性，而面试官通常更关心你的沟通和思路是否清晰。能写出第一版，再把优化思路随口提一句，是最稳妥的策略。
4. 边界条件与隐藏的坑：实测最容易翻车的几种情况
4.1 空数组与单元素数组
空数组这个坑，我在模拟面试里见过太多次了。很多人写第一版代码时不处理空输入，直接进入res[-1]逻辑就会崩。单元素数组虽然不会崩，但也要确保能原样返回。这两者在代码里的体现就是开头的if not intervals: return []，而单元素的情况会自然被主逻辑覆盖，不需要额外分支。千万别为了单元素数组写一堆 if，代码会很难看。
4.2 完全包含型区间：右边界必须取 max
举个例子：
输入: [[1,10],[2,5],[6,9]]排序后还是这个顺序。第一个区间进入结果，第二个区间左端点2小于等于10，右端点取max(10, 5)仍然是10；第三个区间左端点6也小于等于10，合并后还是[1,10]。如果这里不小心用了res[-1][1] = interval[1]，第三个区间就会把右边界从10改成9，整个结果直接错掉。这就是为什么我说“右边界取 max”不是风格问题，而是正确性问题。
4.3 紧邻区间的合并语义：题目约定要提前问
[[1,2],[3,4]]这种，左端点3大于右端点2，正常不会合并。但[[1,2],[2,3]]呢？左端点2等于右端点2，在连续区间语义下应该合并成[1,3]。这个约定如果不确认，建议在动手前明确问一句：“区间是整数点还是连续覆盖？”大多数面试题的隐含条件是连续覆盖，也就是a2 >= b1就算重叠。把这个问题在写代码前提出来，反而会让面试官觉得你思维缜密。
4.4 未排序输入与“看起来有序”的陷阱
有些测试用例会故意长得很“规整”，但中间某个区间乱序。比如[[1,4],[7,10],[3,8]]，如果不排序，你会自认为[1,4]和[7,10]不重叠，结果遇到[3,8]时发现它和前面的合并结果两端都重叠，需要同时回退修改，逻辑就复杂了。更常见的场景是：题目的示例输入恰好是有序的，导致你在练习时忘了排序这一步，换到乱序用例就直接翻车。所以我建议平时练习时，刻意把测试用例的顺序打乱，逼自己养成“先排序”的条件反射。
4.5 我自己踩过的低级失误：比较运算符的边界
我在复盘时发现一个特别容易出错的细节：合并条件到底是interval[0] <= res[-1][1]还是<？如果区间是连续覆盖，等于也应该合并。很多人的第一反应是“不重叠 = 左端点大于右边界”，重叠 =<=，这个没错。但写的时候一紧张就会写成<，导致[[1,2],[2,3]]没合并，输出成两个区间。这种错误不在运行时报错，而是逻辑静默失效，特别难排查。建议你在代码比较处写注释：# 注意是 <=，紧邻也算重叠。
5. 复杂度分析：为什么排序才是这道题的核心成本
5.1 时间复杂度：O(n log n) 的构成
合并区间整个过程可以拆成两个阶段：排序阶段和扫描阶段。扫描阶段是 O(n)，因为每个区间只会被访问一次，结果列表最多操作一次。排序阶段，主流排序算法比如排序和快速排序平均都是 O(n log n)。因此整体时间复杂度是 O(n log n)。这里我经常被人问：能不能降到 O(n)？答案是不能，因为区间合并的结果严重依赖顺序信息，如果输入无序，你至少需要知道全局最小区间和全局最大区间的边界。想要在无序输入下完成合并，等价于要摆脱比较排序的信息论下界，这在常规模型里不可行。
5.2 空间复杂度：结果空间与排序空间的博弈
如果使用额外的res列表，空间复杂度是 O(n)，因为最坏情况所有区间都不重叠，结果列表长度等于输入长度。如果采用原地覆盖法，额外空间可以降到 O(1)。但要注意，主流语言的内置排序并非纯原地。比如 Go 的sort.Slice可能引入 O(log n) 的递归栈，Python 的sort是 Timsort，最坏情况下需要 O(n) 的额外空间。所以“空间复杂度是 O(1)”这个回答要谨慎，最好补充一句“排除排序实现自身的额外开销”。这种严谨的表述，在面试中是很加分的。
5.3 如果输入已经排好序，算法还能加速吗
这个问题是个很好的 follow-up。如果输入已经按左端点有序，那么扫描阶段依然是 O(n)，排序阶段可以跳过，整体变成 O(n)。但要注意一个陷阱：即使左端点有序，右端点不一定有序，你依然需要每步执行max更新，不能只做一次全局右端点扫描。另外，如果输入数据范围有限，比如区间端点只在 1 到 100 之间，可以用桶排序思路把排序阶段优化成 O(n)，但这就属于把问题复杂化了，面试中提到一嘴即可，不建议当成主答案。
6. 面试实战策略：手撕过程中怎么表现出老练
6.1 拿到题的前三十秒，先说哪三句话
我在模拟面试环节总结出一个好用的开场节奏。第一步，先确认输入格式和区间语义：“区间是闭合的连续段吗？紧邻算重叠吗？”第二步，复述一遍自己的思路：“我计划先按左端点排序，再用一个结果列表维护合并后的区间，每次只和最后一个区间比较。”第三步，确认复杂度：“整体 O(n log n)，扫描 O(n)，额外空间 O(n)。”这三句说完，你的思路已经定死了，后面写代码只是把嘴里的方案翻译成语法。即使后面不小心写错一个细节，面试官也会认为这是笔误，而不是思路缺陷。
6.2 手撕期间的写法细节与沟通节奏
写代码时尽量保持“小步走、边写边说”的节奏，不要闷头写完一大段再解释。每写几行就同步说明这一段在干嘛。比如写完排序后说：“这里排序，是为了保证后续扫描时，当前区间的左端点一定大于等于之前所有区间的左端点。”这个习惯很吃香。代码细节上，注意变量命名要清楚，用left、right而不是a、b；写res[-1][1]这种索引时，心里要清楚它是最后一个区间的右边界，嘴上也最好带一句。如果写错了，别慌，先承认：“这里我意识到边界条件要改一下”，然后从旁边重写，不要涂黑整片代码。
6.3 常见的 Follow-up 与扩展变形
面试官做完这道题，通常还会追问两三个变形。我把最常碰到的整理在这：
- 插入区间：给一个已经合并好的区间序列，再给一个新区间，要求插入后仍保持合并状态。做法是先定位再插入，本质上还是合并区间的局部版本。
- 最少移除多少区间才能让剩余区间互不重叠：需要按右端点排序，然后贪心保留最早结束的区间。
- 返回所有区间覆盖总长度：合并后求和各区间长度，就是顺路的事。
- 区间分组：把所有区间分成最少的组，使组内区间互不重叠。答案是统计同一时刻最多重叠区间数。
这些变形其实都是同一个核心思维的迁移：先排序，再按某种顺序贪心地扫描，守恒量是“当前已处理区间的关键边界值”。能把合并区间的这个根讲透，变形题基本白送。
最后分享一个我复盘时的经验：不要只在编辑器里跑成功就结束，建议你亲手列表格，把所有边界用例像 4.1 到 4.4 那样过一遍，再拿变形题练嘴。手撕合并区间不是背代码，而是练一套“排序 + 贪心 + 边界防御”的条件反射，这个反射一旦建立，后续几乎所有的区间类问题都会变得亲切很多。
