1. 先说清楚这道题为什么值得反复刷leetcode 56 合并区间在 leetcode 热门100题里属于那种“看起来人畜无害实际上一伸手就暴露基本功”的题。我身边不少朋友在 leetcode 周赛430 之前临时抱佛脚刷的第一批题单里就有它。你打开题目页描述只有一句话给出一组区间合并所有重叠区间。示例也很友好[[1,3],[2,6],[8,10],[15,18]]合并成[[1,6],[8,10],[15,18]]。很多人看完觉得这不就是个排序吗然后上手一写各种细节翻车。这篇文章想从一个真正刷题做题的人的角度把这道题从读题到 AC、从复杂度分析到面试表述全部过一遍。内容不光是给一个标准答案而是把每一步的选择逻辑、边界处理、常见坑位都摊开讲。不管你是刚刷题的小白还是准备面试想快速过一轮高频题的老手这篇对你应该都有参考价值。1.1 一道“简单不简单”的题我们可以先面对面看一下题目长什么样。输入是一个二维数组里面每一个元素代表一个区间比如[1,3]表示从1到3的闭区间。题目要求输出合并后的区间列表合并的定义是两个区间只要有重叠部分就合成一个新的更大区间。我最早刷这道题的时候第一反应是“暴力两两比较”拿第一个区间和第二、第三、第四个区间比重叠就合然后拿合出来的新区间接着和其他比。这个思路对不对对但是非常蠢。因为区间数量一旦上百两两比较的次数就接近 n 的平方而且合并会产生新区间新区间又可能和之前已经比较过的区间再次重叠整个状态很容易乱掉。后来我才想明白这道题看起来是“区间合并”实际上考察的是两个基本功第一你知不知道排序能改变问题的复杂度第二你能不能处理好“边界相邻”这种细枝末节。说得再直白一点它考的不是你会不会合并两个区间而是你懂不懂把一堆无序的东西整理成有序的然后只用一遍遍历就搞定问题。1.2 面试官想看你什么能力我后来在模拟面试里也拿这道题问过别人发现面试官看重的点其实很固定。第一个是审题是否仔细。题目给的是闭区间[1,3]和[3,5]算重叠因为端点3是共享的。有不少人下意识觉得端点相等不算重叠一写条件就写成curr[0] right才加入新区间这实际上就把[1,3]和[3,5]给拆开了结果必然错误。第二个是对排序的敏感度。很多人看到区间就想着用 map 或者 set 去重其实完全绕远了。排序的好处是把原本散乱的重叠关系变成一种“单调”的关系左端点一旦有序后面的区间只可能和当前已经合并出来的区间发生重叠不可能回头和更早的区间重叠。这一步想通了后面就顺理成章。第三个是对复杂度的表达。一个合格的回答至少应该主动说出“时间 O(n log n)空间 O(n)”而不是等面试官追问才挤出来。能把排序的代价讲清楚说明真的有分析意识。2. 核心思路是怎么一步步长出来的思路这东西直接看题解很容易但如果不理解它为什么成立换个变体题型照样懵。我们从头捋一遍看看“排序加单次扫描”这一步到底是怎么自然生长出来的。2.1 暴力合并为什么不行先假设输入是[[1,4],[2,5],[7,8],[3,9]]。肉眼一看[1,4]和[2,5]重叠[2,5]和[3,9]也重叠所以最后应该合并成[1,9]再加上[7,8]被包含在内最终答案是[[1,9]]。如果我们不排序直接用暴力法先拿[1,4]去找其他区间找到[2,5]合并成[1,5]接着拿[1,5]继续找找到[7,8]不重叠再遇到[3,9]发现重叠合并成[1,9]。跑完一轮你以为结束了不对[7,8]是在合并[1,5]时已经被“判过不重叠”的但后来合并出[1,9]之后它又被包含了。所以暴力做法要么得反复扫描要么得额外记录状态最坏情况下来回好几轮复杂度直接 O(n²) 起步代码还特别乱。我当时就体会到问题出在“区间的合并顺序不确定”。两个区间隔得很远结果它们因为中间的区间链式传递最终重叠了这种关系在无序状态下很难一眼看穿。所以核心需求其实是先让所有区间的左端点排好队让重叠关系的判断变得有序化。2.2 排序是这道题的破局点假设所有区间都按左端点从小到大排好了例如[[1,5],[2,4],[3,6],[8,10]]。这时候有一个关键性质当前区间只可能和它前面已经合并出来的那个大区间重叠不可能和更早的区间重叠。为什么因为后面每一个新区间的左端点都比前一个大如果当前区间start已经大于前一个合并区间的end那么后面所有的区间start只会更大更不可能和前面那个合并区间重叠了。这就像你打扫房间只要把地上的东西按尺寸排成一排扫过去一遍每个地方只需要看一次不用来回折返。有了这个性质解法就是维护一个“当前合并区间”从前往后遍历每看到一个新区间就判断它的左端点是否小于等于当前合并区间的右端点。如果是说明重叠更新右边界如果不是就把当前合并区间收进答案然后把新区间作为新的合并区间继续走。这一步做完区间合并的所有复杂度都集中在了排序上排序 O(n log n)扫描 O(n)整体 O(n log n)。这种把“无序关系”转化为“有序单调关系”的思路才是这道题真正的价值所在。3. 手把手写出标准解法思路通了写代码就只是把思路翻译成语法的事了。我给两个常用版本一个是 Java一个是 Python然后把执行过程推演一遍。3.1 完整代码与执行过程推演先上 Java 版本。我比较推荐在面试时用 Java 写因为工程岗位普遍用 Java而且它的Arrays.sort对二维数组的排序写法能直接展示你对语法的熟练度。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 curLeft intervals[0][0]; int curRight intervals[0][1]; for (int i 1; i intervals.length; i) { if (intervals[i][0] curRight) { curRight Math.max(curRight, intervals[i][1]); } else { merged.add(new int[]{curLeft, curRight}); curLeft intervals[i][0]; curRight intervals[i][1]; } } merged.add(new int[]{curLeft, curRight}); return merged.toArray(new int[merged.size()][]); } }我们拿官方示例[[1,3],[2,6],[8,10],[15,18]]手推一遍。排序后区间顺序不变初始化curLeft1, curRight3。遇到[2,6]因为2 3合并curRight更新为max(3,6)6。此时合并区间是[1,6]。遇到[8,10]因为8 6说明不重叠把[1,6]加入结果同时当前区间重置为[8,10]。遇到[15,18]15 10再加入[8,10]重置为[15,18]。循环结束最后再把尾巴上的[15,18]加入结果。最终得到[[1,6],[8,10],[15,18]]。这里有个容易被忽略的细节循环结束后最后一个区间一定还没被放进去必须在方法末尾再add一次。我在初学时就漏过这一步导致结果总是少最后一个区间。如果你用从 0 开始遍历的写法也要在末尾处理收尾始终记住“当前区间在遇到不重叠区间时才结算”这个节奏。3.2 换一门语言Python 版本与答题节奏建议如果你用 Python代码可以更短核心逻辑一模一样只是换了一些语法糖。from typing import List class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: if not intervals: return [] intervals.sort(keylambda x: x[0]) res [] for interval in intervals: if not res or res[-1][1] interval[0]: res.append(interval) else: res[-1][1] max(res[-1][1], interval[1]) return resPython 里这个写法的巧妙之处在于它把“当前合并区间”直接放在res的最后一个位置里。每次循环先看res[-1]如果和当前区间不重叠就追加新区间如果重叠就原地修改最后一个区间的右端点。注意这里的判断条件是res[-1][1] interval[0]才追加也就是只有在“严格不相交”时才开新段只要右端点大于等于当前左端点都算重叠等价于 Java 版本的interval[0] curRight。关于面试答题节奏我个人的经验是不要上来就闷头写代码。先说一句“这种区间问题我习惯先排序”然后解释排序后为什么一遍扫描就够最后再动手写。这样面试官能感知到你不是背题而是真的理解思路。写完之后再用刚才的示例简单跑一遍同时把复杂度说出来。整个流程控制在三到五分钟非常加分。4. 复杂度、边界与性能上容易翻车的点代码能 AC 只是第一步面试和实际工作里还会追问各种细节。这一节把复杂度和边界问题集中说清楚。4.1 复杂度到底怎么算才不会被问倒先看时间。排序是主要开销一般的快速排序或归并排序是 O(n log n)。扫描阶段只遍历了数组一次每次操作是常数时间的比较和更新所以是 O(n)。合在一起O(n log n n)通常直接说 O(n log n)。因为 n 够大时排序项占主导n 很小时扫描那点开销无所谓。空间方面最坏情况下没有任何区间重叠res要装下所有 n 个区间额外空间 O(n)。但这里有个小细节返回值本身占用的空间在多数分析中不计入“额外空间”面试官如果追问你就说“额外空间主要用于结果数组最坏 O(n)排序内部如果用的是 TimSort 还需要 O(n) 的临时空间”。你主动讲出这一层会显得对底层机制有了解。另外很多人问“有没有可能把时间压到 O(n)”。如果区间端点的取值范围很小理论上可以用差分数组或桶排序的思路先统计每个端点的覆盖次数再扫描端点得到合并段。现实中绝大多数题的区间端点都是任意整数范围可能达到几亿差分数组不可行。所以 O(n log n) 就是这个问题的标准最优复杂度。面试时如果有人问“能不能优化到线性”你可以提一下这个思路并说明限制比直接说“不能”显得更有思考。4.2 边界条件与输入校验边界条件不是玄学就是把每种输入形态都过一遍。第一种是空输入[]。Java 版本直接返回原数组Python 版本返回空列表都没问题。第二种是只有一个区间[[5,6]]不需要合并原样返回。第三种是全包含的情况比如[[1,10],[2,3]]排序后先设curLeft1, curRight10遇到[2,3]时2 10更新curRight max(10,3) 10保持不变结果正确。第四种是端点相邻[[1,2],[2,3]]因为2 2成立合并成[1,3]这符合题目闭区间的定义。还有一类隐藏边界是单点区间[[1,1],[1,1]]。两个相同的区间重叠应该合并成一个[1,1]。代码里1 1更新右端点为max(1,1)1结果正确。我建议在本地准备一套测试用例表每次写完都跑一遍既验证逻辑也能在面试时展示自己的严谨程度。后面我会专门列一张测试用例清单。5. 我踩过的坑与排查实录这节从真实踩坑记录讲起很多错误不是不会写而是写的时候惯性思维太强。5.1 最容易出的三类错误第一个坑是忘记排序。看起来不可思议但真有人上来就维护一个current区间开始扫描结果遇到[[1,4],[0,2],[3,5]]直接错。因为不排序的话[0,2]虽然和[1,4]重叠但它出现在后面等你扫到它时当前的合并区间可能是[1,4]你会把它合并成[0,4]接着遇到[3,5]合并成[0,5]。好像也能过再换个例子[[1,2],[0,1],[4,5]]不排序时会先处理[1,2]然后[0,1]并入变成[0,2]接着[4,5]不重叠结果变成[[0,2],[4,5]]好像也对。但只要例子换成[[3,6],[1,2],[2,4]]不排序就会先处理[3,6]遇到[1,2]不重叠加入结果遇到[2,4]和前面的[3,6]合并成[2,6]但[1,2]和[2,6]其实也相邻最终结果应该是[[1,6]]。这就错了。所以排序不是形式是正确性的前提。第二个坑是右边界更新没有用max。比如[[1,5],[2,3],[4,6]]第一次合并[1,5]和[2,3]如果代码写成curRight intervals[i][1]curRight 会从 5 变成 3区间反而变小了后面的[4,6]就被判断为不重叠结果错得离谱。正确写法永远是Math.max(curRight, intervals[i][1])。这个错误本质上是对“合并区间取并集”的理解不到位并集的右端点必须是两个区间右端点的最大值。第三个坑是排序比较器里的减法溢出。Arrays.sort(intervals, (a, b) - a[0] - b[0])在大多数情况下没问题但如果左端点是极端值比如Integer.MAX_VALUE和Integer.MIN_VALUE减法结果会溢出导致排序错乱。安全的写法是Integer.compare(a[0], b[0])或者自己写if (a[0] ! b[0]) return a[0] b[0] ? -1 : 1;。虽然实际算法题里很难构造这种极端数据但面试官问到“你为什么要用 compare 而不是减法”时这是一个很好的加分点。5.2 测试用例怎么设计才全面我把常用测试用例整理成了一张表建议直接拿来用用例编号输入期望输出覆盖点1[[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]官方示例部分重叠2[[1,4],[4,5]][[1,5]]端点相邻算重叠3[[1,4],[2,3]][[1,4]]包含关系4[[1,2],[3,4]][[1,2],[3,4]]完全不重叠5[[1,1],[1,1]][[1,1]]单点重复区间6[][]空输入7[[5,5]][[5,5]]单个区间8[[2,3],[1,6],[5,7]][[1,7]]链式合并、乱序输入你把这八条用例在本地跑一遍代码的正确性基本就稳了。用第 7 条这种“只有一个区间”的用例很多人会忘记 Java 里length 1的早退分支导致越界用第 8 条可以验证排序对乱序输入的兜底作用。6. 从这一题看整个“区间问题家族”合并区间不是孤立存在的题它是一类题的入口。搞懂它之后你会发现在 leetcode 上有一大批区间题的核心骨架都非常相似。6.1 高频变种题一网打尽leetcode 435 无重叠区间是最直接的变种。题目要求给定一组区间移除最少的区间让剩余区间互不重叠。思路是排序后贪心每次遇到重叠区间保留右端点更小的那个。为什么保留右端点小的因为右端点越小给后面区间留下的空间越大。这比合并区间多一层“选哪个区间保留”的思考但排序和扫描的框架一模一样。leetcode 57 插入区间则是另一个方向的变形给你一个已经按左端点排好序且互不重叠的区间列表再给你一个新的区间你把它插入进去合并后的结果也要保持有序且不重叠。做法可以先把新区间按位置插进去然后复用合并区间的扫描逻辑也可以直接在遍历过程中找到插入位置边插入边合并。核心还是“判断重叠更新边界”。leetcode 252 会议室要求判断一个人能否参加所有会议本质就是判断一组区间是否互不重叠。排序后扫一遍一旦发现某个会议的开始时间早于上一场会议的结束时间就返回 false。这就是合并区间扫描逻辑去掉合并动作后的简化版。leetcode 452 用最少数量的箭引爆气球把区间换成了气球直径范围要求用尽量少的箭射穿所有气球。解法其实是在找“重叠区间的公共交集个数”排序后维护一个当前射击区间的右端点遇到新区间就判断是否还能共用一支箭。思路和合并区间几乎同源。这四个题如果连起来刷你会发现它们其实是在同一套“排序 单次扫描 边界维护”框架下更换不同的判断条件。所以我才会说56 合并区间是整个区间问题家族的地基。6.2 合并区间在实际业务系统里的影子刷题不能只为了面试这道题的思路在真实业务里也很常见。日历应用就是个典型场景。一个用户可能从多端同步了很多日程片段比如出差行程、会议、个人安排后端常常拿到一堆时间区间需要先合并重叠的时间段再展示给前端避免界面上出现“两个会议重叠”的诡异状态。合并逻辑就是今天讲的这道题。日志分析也常碰到。比如一个请求的访问日志分散在多个时间碎片里需要把同一请求的访问区间合并成几个大段方便做耗时统计。还有广告系统的展示时段合并、优惠券活动时间段的冲突处理本质都是一样的区间合并问题。网络工程师用 CIDR 表示 IP 段时也需要把多个连续的 IP 段合并成更大的段来简化路由表规则。把 IP 段映射成整数区间然后按左端点排序、合并和这道题完全一致。所以别小看这一道题它背后是一整套区间数据处理能力的缩影。7. 最后再说说我的答题习惯我自己刷高频题有个习惯不急着看题解而是先自己想清楚“这题如果不用排序能不能做”再想“排序之后能不能简化”最后再看别人的解法对照。反复练过几次之后再遇到区间类题型我会下意识先问一句“输入是有序的吗”这短短一句话很可能决定了解法方向。另外一个小建议是动态语言写算法题很爽但如果你在 Java 环境里写两维数组的转换toArray(new int[merged.size()][])这个写法要背熟很多人在面试现场会卡在这一行。我当初就是被这个 API 憋住过后来干脆在本地多敲了几遍形成肌肉记忆。还有一点想提醒的是不要满足于“能 AC”。试着把代码里的curLeft和curRight换成只用一个区间对象来维护或者试试 Python 里直接改res[-1]的写法你会发现不同代码风格对同一个逻辑的表达差异很大。把这几种写法都想过一遍你对这道题的理解会更深。我到现在偶尔还会拿这道题做热身刷一遍原题再顺手看看 435 和 57。每次都有点小收获这可能就是经典题的意义吧。