说实话LeetCode 56这道题属于那种“看着简单、一写就飘”的典型题目。合并区间这四个字初学者会觉得不就是比大小吗真上了面试白板或者被扔进周赛第三题的题解里你会发现细节全在边界和排序策略里。我这篇就把这题的完整拆解、实现细节、易错点、变体思路一次说透。1. 先想清楚一个问题为什么“合并”本身不是考点很多人拿到这题第一反应是“遍历一遍能合并就合并”于是直接开始写两个for循环硬搓。结果往往是把简单问题搞成O(n²)的复杂度还容易在边界上翻车。我先把最核心的逻辑单独拎出来说清楚。假设现在有两个区间分别叫[a, b]和[c, d]判断它们能不能合并条件只有一个如果c b说明这两个区间存在重叠或者相邻可以合并成一个[min(a, c), max(b, d)]。如果c b说明中间有缝隙合并不了。注意这个“c b”的细节是很多题的隐藏考点。LeetCode 56对重叠的定义是“闭合区间”也就是说[1, 3]和[3, 5]这种头尾相接的区间也视为可以合并结果是[1, 5]。如果你写的是c b这两个区间就不会合并答案直接错掉。再往深一层说区间之间还有三种关系需要区分完全不重叠[1, 2]和[3, 4]两头不沾保持原样。部分重叠[1, 3]和[2, 5]有交集合并为[1, 5]。完全包含[1, 6]和[2, 4]后者被前者整体包住合并结果还是[1, 6]。很多人写代码时只处理了前两种遇到完全包含的情况就晕了。比如维护了一个current区间遍历到下一个区间时发现它的右端点比current的右端点还小这时候不该更新右端点否则会把区间拉长得到错误结果。所以合并逻辑本身真的不复杂复杂的是你用什么顺序去处理这些区间以及你的数据结构能不能让你在处理过程中不迷路。这就要引出最关键的一步了。2. 真正的分水岭排序策略的选择做这道题之前你必须在心里确认一个事实如果给你一组乱序的区间你直接遍历是没办法稳定合并的。原因很简单合并是一个“依赖邻居”的操作你只有知道了“谁在谁左边”才能确定合并的先后顺序。所以排序是前置条件不是可选优化项。这一步没想明白后面全是稀里糊涂。2.1 为什么排序后只需盯住右端点按左端点从小到大排序之后会有一个特别好的性质因为后面的区间左端点一定不小于前面的左端点所以在合并时新合并区间的左端点永远保持为当前区间的起点的左端点不需要比较、不需要更新你需要关心的只有一件事——右端点是否要被拉长。这句话值得再念一遍。排序前合并时要同时比较左端点和右端点排序后左端点被锁死了所有决策全部集中到右端点这一个变量上。打个比方你有一排书架每本书的起始位置和结束位置都写在书脊上乱序时你根本不知道哪本挨着哪本。但你把所有书按起始位置从左到右排好之后你只需要从头往后扫一遍看到哪本书的起始位置在当前“已合并段”的结束位置之内就说明它是连着的直接把它纳入进来并更新结束位置就行。这个思路爽就爽在一次遍历、O(n)搞定。2.2 错误排序方向的代价我知道有相当一部分人第一直觉是“按右端点排序”。这也不是不能做但你会发现合并逻辑马上变得棘手排序后右端点有序但左端点是乱的你可能合并出[10, 20]后又遇到[1, 15]它明明应该和前面的区间合并却因为遍历顺序问题被你当成一个新区间处理了。不信你拿[[1, 4], [0, 2], [3, 5]]这个用例试验一下。按左端点排序输出是[[0, 2], [1, 4], [3, 5]]一路顺风合并成[0, 5]。按右端点排序输出是[[0, 2], [1, 4], [3, 5]]不右端点排序会变成[[0, 2], [1, 4], [3, 5]]其实都一样因为数据太巧了。你换一组[[2, 3], [1, 2], [0, 1]]按右端点排完是[[0, 1], [1, 2], [2, 3]]还能合并。但你再试试[[1, 10], [2, 3], [4, 5]]按右端点排序变成[[2, 3], [4, 5], [1, 10]]直接从第一个区间开始扫描发现第二个和第三个区间的左端点都在当前右端点之外于是错误地分成三个区间。可实际上这三个区间都能合成一个。这就是排序策略选错的典型恶果你不是不能做而是需要额外的回溯逻辑来修正复杂度直接上升。按左端点排序则天然避免了这个问题遍历过程就像拉链一样一路咬合过去。2.3 关于排序稳定性的一句话如果两个区间左端点相等那么排序时它们谁先谁后其实无所谓因为合并结果是一样的。所以用Arrays.sort默认的归并排序稳定或者快速排序不稳定对本题结果没有任何影响。这一点不用过度纠结。3. 手写实现从第一版到能过所有用例我直接给你一份能提交通过的Java版本然后一行一行说为什么这么写。class Solution { public int[][] merge(int[][] intervals) { if (intervals null || intervals.length 0) { return new int[0][2]; } // 按区间左端点升序排序 Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] merged new ArrayList(); int[] current intervals[0]; merged.add(current); for (int i 1; i intervals.length; i) { int[] next intervals[i]; if (next[0] current[1]) { // 重叠或相邻更新当前合并区间的右端点 current[1] Math.max(current[1], next[1]); } else { // 不重叠开启新区间 current next; merged.add(current); } } return merged.toArray(new int[merged.size()][]); } }你自己动手写第一版的时候最容易错的三个地方我给你全列出来。3.1 易错点一更新右端点时用了min而不是max这是初学者最常见的手误。你的current右端点如果比next的右端点大说明next被完全包含这时候不能把右端点改成小的否则区间缩短后面再来一个区间可能就被错误地判定为不重叠。所以这里必须取Math.max宁可让区间暂时“虚胖”也不能让它“缩水”。3.2 易错点二用排序后的原始二维数组直接改造成源数据被破坏有人在合并时喜欢直接修改intervals[i]的值比如intervals[i][1] Math.max(intervals[i][1], intervals[i - 1][1]);这样写完会发现逻辑上能跑但如果你后面还需要原始区间做别的事或者测试框架里对你传入的数组做断言数据已经被改了。更重要的是这种写法在可读性上很差面试官一眼就能看出你对“可变状态”的管理不够敏感。更稳妥的做法是像我的示例代码一样用一个merged容器来收集结果current作为哨兵区间不断更新它的右端点。注意我merged.add(current)添加的是引用后续修改current[1]会同步反映到列表里所以不需要再单独维护一个“最后结果的右端点”变量。3.3 易错点三toArray的用法写错Java里Listint[]转二维数组正确写法是merged.toArray(new int[merged.size()][]);有人会写new int[0][]也能跑但会在内存里多分配一次。面试时可以顺手写成new int[merged.size()][]显得你考虑过容量问题。当然toArray本身有扩容机制写new int[0][]也不会错只是敏感一点的人会注意到这种微小差异。如果你平时写Python这道题的实现会更简洁class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: if not intervals: return [] 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 merged注意Python版本里判断条件是merged[-1][1] interval[0]意思是当前区间的右端点够不到下一个区间的左端点属于“隔开”的情形此时才新建区间否则直接合并并更新右端点。逻辑上跟Java版本完全等价只是表达顺序反过来。4. 复杂度与边界别小看这些“显然”的问题LeetCode上这题标的是Medium但它之所以不是Easy不是因为合并逻辑有多绕而是因为你要意识到排序带来的复杂度占比以及边界用例的多样性。4.1 时间复杂度到底看哪一部分排序的时间复杂度是O(n log n)合并遍历是O(n)。所以整体是O(n log n)其中n是区间数量。空间复杂度方面如果按题目要求输出一个新的二维数组那么需要O(n)的额外空间来存结果如果你在原数组上改理论上是O(1)额外空间抛开排序栈消耗但实际工程中没人这么干因为破坏入参不是一个好习惯。很多人分析到这里就停了但我建议你再想一层这个O(n log n)里常数大不大其实很大因为二维数组排序的比较器涉及数组元素访问会比一维数组排序更慢。这也是为什么面试官有时候会问“你能不能想出不用排序的做法”本质上是在试探你能否权衡预处理成本和后续处理成本之间的关系。4.2 边界用例清单我每次做这道题都会先在脑子里过一遍这些边界场景示例预期输出空数组[][]单区间[[1, 2]][[1, 2]]完全相同[[1, 5], [1, 5], [1, 5]][[1, 5]]包含关系[[1, 6], [2, 4], [3, 5]][[1, 6]]首尾相接[[1, 2], [2, 3], [3, 4]][[1, 4]]全部分开[[1, 2], [3, 4], [5, 6]][[1, 2], [3, 4], [5, 6]]负数区间[[-5, -1], [-3, 0], [2, 4]][[-5, 0], [2, 4]]极端大值[[0, 0], [0, 10], [10, 100]][[0, 100]]这些用例在本地跑一遍基本就能确认代码的鲁棒性。我特别提到负数区间是因为很多人写比较器时直接用a[0] - b[0]这在绝大多数场景没问题但如果左右端点都是非常大的整数比如Integer.MAX_VALUE和Integer.MIN_VALUE相减会溢出导致排序结果错误。严谨一点应该用Integer.compare(a[0], b[0])。推荐直接改成Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));别小看这一行它能帮你规避掉一个极其隐蔽的整数溢出bug。面试时写出来还能顺手展示你对API的熟悉度。5. 从一道题看一类题区间问题家族合并区间是区间类问题的基础原型。你把它吃透了后面好几个题都能顺藤摸瓜所以我多花点篇幅把这串题的关系理清楚。5.1 一道题延伸出的变体对比我把LeetCode上常见的区间类题目整理成一张表方便你对比它们的差异题目核心操作与56题的关系56 合并区间把重叠区间合并原型注重“排序单次扫描”57 插入区间给定有序区间插入一个新区间再合并排序步骤被省略/简化为二分查找核心仍是合并435 无重叠区间移除最少区间使剩余区间互不重叠同样需要排序但“贪婪”策略相反452 用最少数量的箭引爆气球实际上是“最多重叠区间数”问题排序后贪心但判断条件和56相反1288 删除被覆盖区间统计有多少个区间被其他区间完全覆盖依赖包含关系的判断恰好是56排序后要处理的情况986 区间列表的交集两个有序区间列表求交集双指针扫描不用排序但区间比较逻辑相通你会发现区间类题目最核心的就三件事排序、比较两个区间的位置关系、用贪心或扫描维护一个“当前状态”。5.2 从56过渡到57插入区间的隐藏坑57题是“给你一个已按左端点排好序的区间列表再给你一个新区间把新区间插入进去并合并”。很多人直接复用56的方法先把新区间塞进列表再整体排序、合并。这当然能过但时间复杂度变成O(n log n)而题目本身因为输入有序其实可以O(n)解决。正确的思路是这样遍历已排序的区间列表把所有在新区间左侧且不相交的部分直接加入结果然后开始处理重叠部分不断用新区间和当前遍历到的区间比较更新新区间的左右端点处理完所有重叠者后把新区间加入结果最后把剩下的右侧区间直接加入结果。这个过程中用到的合并逻辑跟56完全一样差别只在于你已经站在一个有序列表上遍历所以少了排序这一步。如果你能在面试时主动说出“因为输入已经有序这里可以优化到O(n)”这比单纯写出代码更容易加分。5.3 从56过渡到435为什么同样是贪心做法完全不同435要求移除最少的区间使剩余区间互不重叠也常用贪婪算法但判断逻辑是按右端点排序总是选择右端点最小的区间作为保留对象然后遍历其余区间跳过所有和它重叠的。这样能保证留下的区间最多从而移除的最少。对比56你会发现56按左端点排序合并时关注右端点能不能被拉长435按右端点排序保留时希望右端点尽量小给后面的区间留空间。同样是“排序贪心”一个往大合并一个往小收缩方向正好相反。这个反差特别能考验你对问题本质的理解。我建议刷题时把这个串烧放在一起做做完56马上做57、435、452你会明显感觉到“哇原来都是一个套路的不同用法”。6. 面试实战几个隐含考点不是LeetCode会告诉你的我在面试中问过这道题也被别人问过这道题给你交个底面试官真正想看的东西是什么。6.1 千万别急着写代码先画图面试白板上如果你上来就写Arrays.sort面试官心里可能已经在扣分了。他们更希望看到你先举例、画示意、口头描述合并逻辑然后再说“我打算先按左端点排序再用一次扫描完成合并”。这个过程体现的是结构化思维而不是背题能力。我自己面试候选人时如果对方花两分钟画了一下区间重叠的图再说出排序策略我基本已经给这道题的代码分了。因为后面的代码只是把这个思路翻译成语法而已。6.2 关于排序比较器的讨论Java里Arrays.sort(intervals, (a, b) - a[0] - b[0])能写但如果你用Integer.compare并解释一句“防止整数溢出”这就是一个主动展示工程经验的moment。这两个写法在LeetCode的测试数据里可能都AC但在面试环境下你展现出的细致程度会直接拉开差距。6.3 能不能原地合并多数人答不好面试官可能会追问“能不能不借助额外容器直接原地合并”答案是可以但需要你用一个指针idx指向合并结果填到哪里class Solution { public int[][] merge(int[][] intervals) { if (intervals null || intervals.length 0) { return new int[0][2]; } Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); int idx 0; for (int i 1; i intervals.length; i) { if (intervals[idx][1] intervals[i][0]) { intervals[idx][1] Math.max(intervals[idx][1], intervals[i][1]); } else { idx; intervals[idx] intervals[i]; } } return Arrays.copyOf(intervals, idx 1); } }这里的关键是被合并掉的区间所占的位置会被跳过我们不断把“新的不重叠区间”搬到数组前部最后用Arrays.copyOf截断多余部分。这种写法空间上更省但破坏了入参数组的顺序结构。面试时如果你能主动说出“我可以原地合并但代价是修改了入参工程上一般不推荐”这一句话就包含了几层意思你会优化、你懂取舍、你了解工程习惯。6.4 和输入流结合如果区间是流式到达呢有一个进阶讨论可能不在LeetCode范围内但偶尔会被问到如果区间不是一次性给你而是一个一个到达的怎么维护合并结果答案是维护一个有序结构比如TreeMap键是左端点值是右端点每次插入新区间后找到可能的重叠区间并合并。插入和合并都是O(log n)级别整体可以接受。这个思路本质上是把静态排序变成了动态插入排序。能说出这一层说明你举一反三的能力到位了。7. 复盘与最终建议我不知道你刷这道题处于什么阶段。如果是刚开始接触区间类问题我建议你至少手写三遍第一遍看着题解写第二遍合上书自己写第三遍用不同的语言或不同写法比如原地合并再写一遍。三遍下来你对排序加扫描这个模板基本就形成肌肉记忆了。如果是准备面试我建议你在写完这道题之后把57、435、452这三个题连着刷并且每做一题都回头问自己“如果输入已经有序我会怎么改如果数据是流式的我又会怎么改”能把这两个问题的答案脱口而出你在这类题上的掌握程度就已经超过绝大多数候选人了。我在实际项目部里面代码评审时见过有人把这道题的逻辑用得很巧——处理时间区间、处理IP段合并、处理日程表冲突检测都是一个套路先排序、再扫描、维护当前边界。所谓“合并区间”看起来是在解决一道算法题实际上是在解决现实里最普通不过的归并问题。想通这一层LeetCode 56就不仅仅是一道题了它会沉淀成你处理连续数据问题的底层思考方式。最后分享一个小技巧在你写任何区间类题目之前先在注释里画三个区间标上重叠、包含、分离三种关系然后再动笔。这个习惯帮我省掉的debug时间比我写任何代码都快。