如果你刷过力扣热题100会发现“合并区间”基本是绕不开的一道题。它在题库里的编号是56热度常年不减面试出镜率极高。很多同学觉得它简单不就是排个序再扫一遍嘛但真正到了面试或者周赛里边界条件、重叠判断、原地修改这些细节一旦没想清楚很容易翻车。这篇内容我就以这道题为切入点把解题思路、代码实现、常见坑点以及它在热题100中的定位一次讲透希望能给正在刷题或者准备面试的你一些参考。1. 先说清楚合并区间到底在考什么1.1 题意回顾热题100中的这道高频题题目描述非常简洁给定一个区间的集合数组中每个元素是一个长度为2的数组形如 [start, end]表示一个左闭右闭区间。如果两个区间之间存在重叠部分就把它们合并成一个新区间。要求返回合并后的区间列表并且最终结果里的区间不能重叠还需要按每个区间的起始位置升序排列。举个例子输入是 [[1,3],[2,6],[8,10],[15,18]]因为 [1,3] 和 [2,6] 有交集合并成 [1,6]而 [8,10] 和 [15,18] 之间没有任何交集原样保留所以输出是 [[1,6],[8,10],[15,18]]。这个例子基本包含了题目的所有考点判断重叠、执行合并、保持顺序。但要注意题目给的输入列表不一定有序换句话说区间是乱序出现的比如可能给你 [[2,6],[1,3],[15,18],[8,10]]这也是热题100里很多区间类题目共同的特点——输入无序需要我们自己对数据先做预处理。1.2 出题人真正想考察的是什么我先说一个自己的判断这道题表面上考的是“合并”实际上考的是“排序 贪心 区间思维”。面试官在让候选人写这道题的时候第一眼想看的往往不是你会不会调库而是你能不能快速发现“排序是解决区间重叠问题的前置条件”。很多无序区间问题在排完序之后会瞬间变得清晰这是区间类问题最核心的套路。排序之后我们只需要依次比较当前区间的左端点和结果集最后一个区间的右端点就能判断是否存在重叠整个过程一次遍历搞定复杂度为 O(n log n)。这个思想在热题100的其他题目里也反复出现比如会议室问题、插入区间、用最少数量的箭引爆气球等本质上都是同一套思想。所以说合并区间是区间类题目的敲门砖一点都不夸张。2. 核心方法论为什么排序是这题的第一性原理2.1 区间重叠的条件与排序的关系先回到一个基础问题上两个左闭右闭区间 [a, b] 和 [c, d]什么时候算重叠按集合论的定义只要它们有公共点即满足 c b 且 a d 就是重叠。但如果把两个区间按起点排好序保证 a c那么重叠条件可以进一步简化为 c b也就是说后一个区间的起点只要不超过前一个区间的终点两个区间就一定有重叠部分。这个简化看起来微不足道却是整个算法的支点。没排序的时候要两两比较区间暴力做法是 O(n^2) 的双重循环而且合并完还可能产生新的重叠要反复循环排序之后线性扫描一次就能解决从 O(n^2) 直接降到了排序的 O(n log n)。我常给刷题的朋友打个比方如果一堆人的生日散乱地写在纸条上你要找出日期连续重叠的所有人最常见的方式就是先把纸条按照日期从小到大排好再一组一组看。排序让一个原本无序的二维问题降维成了一维的有序比较问题。2.2 贪心思想在这里的落地排序之后选择什么样的合并策略这就要用到贪心了。我们把区间按起点从小到大排序然后维护一个结果列表。遍历每个区间时看当前区间能不能和结果列表里最后一个区间合并。这里有一个关键点结果列表里的最后一个区间是所有已经处理过的区间中“最右边”的一个因为后面的区间起点只会更靠后。所以只要当前区间的 start 小于等于结果列表中最后一个区间的 end那就说明产生了重叠。此时需要做的不是新建区间而是把结果列表最后一个区间的 end 更新为两者 end 的较大值。为什么取较大值因为虽然起点有序但终点不一定有序。比如第一个区间是 [1,10]第二个区间是 [2,3]第二个被完全包裹在第一个里合并后的终点仍然是 10而不是 3。这是新手最容易出错的地方后面我会专门展开讲。如果当前区间的 start 大于结果列表最后一个区间的 end说明它们完全分离此时才需要把当前区间作为一个全新的区间加入结果列表。这样处理的逻辑本质上是每一步都保留“当前合并后最靠右的终点”贪心地让已合并区间尽可能地覆盖更多后续区间最终达到合并所有重叠区间的最优结果。2.3 复杂度分析为什么排序是最优解的前置步骤从复杂度角度看排序是 O(n log n)一次遍历是 O(n)所以整体时间复杂度是 O(n log n)。空间复杂度方面排序通常会消耗 O(log n) 的递归栈空间如果不允许修改原数组用来存储结果列表还需要 O(n) 的额外空间如果允许原地修改输入数组那空间上能省一点但通常面试中不纠结这一点。有同学问能不能不排序直接做我见过一些另类思路比如用哈希表记录覆盖范围、用图论找连通分量但都会把问题复杂化而且时间复杂度并不会更优。在 n log n 已经是比较排序理论下界的情况下排序是所有常规解法里最干净、最好写的。对于这道题面试官期待看到的就是排序加一次遍历而不是花里胡哨的黑科技。3. 题解实现合并区间常规解法三步走3.1 第一步边界处理与排序的细节写代码之前先把边界条件想清楚。常见的输入情况有三种空数组、只有一个区间、有多个但完全无序。空数组直接返回空列表这是 LeetCode 上必须处理的情况否则后续访问会越界。只有一个区间的数组不需要合并原样返回即可。排序本身也有细节。Java 和 Python 里可以很方便地对二维数组做排序但是要给比较器或者 key 参数指定排序依据否则默认按字典序排排序结果可能不符合预期。Python 写法很简单intervals.sort(keylambda x: x[0])表示按每个区间的起始值排序Java 需要使用Arrays.sort(intervals, (a, b) - a[0] - b[0])C 则常用sort(intervals.begin(), intervals.end())因为vectorpairint,int或者vectorvectorint默认会按第一个元素排序。这里提醒新手如果输入是int[][]且区间宽度固定为2直接使用默认的字典序排序导致的问题不大但为了语义清晰最好显式指定按起点排序。这样代码的可读性更好面试时也更容易讲清楚自己的思路。3.2 第二步一次遍历完成合并的核心逻辑排序完成后核心逻辑就非常简洁了。我们可以维护一个结果列表merged先把排序后的第一个区间放进去然后从第二个区间开始遍历。每次取当前区间cur同时观察结果列表最后一个区间last。如果cur[0] last[1]说明两个区间有重叠那么我们执行合并更新last[1] max(last[1], cur[1])注意这里必须取最大值因为可能出现包含关系。如果cur[0] last[1]说明当前区间和已有的所有区间都没有重叠由于排序保证后续也不可能和之前的其他区间重叠直接merged.append(cur)。这个遍历过程中有个隐含性质因为结果列表里的区间已经按照起点排序而且每次合并后我们都尽量把终点往右扩展所以结果列表中的区间始终是有序且互不重叠的。确认了这一点整个算法可以放心运行到最后。3.3 第三步代码落地Python / C / Java 片段我先给出最常用的 Python 实现这也是我在 LeetCode 上提交通过率最高的版本def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for cur in intervals[1:]: last merged[-1] if cur[0] last[1]: last[1] max(last[1], cur[1]) else: merged.append(cur) return mergedC 实现可以这么写这里使用的是vectorvectorintclass Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint merged; merged.push_back(intervals[0]); for (int i 1; i intervals.size(); i) { vectorint last merged.back(); if (intervals[i][0] last[1]) { last[1] max(last[1], intervals[i][1]); } else { merged.push_back(intervals[i]); } } return merged; } };注意这里的vectorint last用的是引用目的是直接修改merged中最后一个区间的终点。如果忘记加引用修改的只是副本会导致合并结果完全不生效。这一点是很多从 C 入门刷题的同学容易踩的坑。Java 版本实现如下class Solution { public int[][] merge(int[][] intervals) { if (intervals.length 0) return new int[0][2]; Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] merged new ArrayList(); merged.add(intervals[0]); for (int i 1; i intervals.length; i) { int[] last merged.get(merged.size() - 1); if (intervals[i][0] last[1]) { last[1] Math.max(last[1], intervals[i][1]); } else { merged.add(intervals[i]); } } return merged.toArray(new int[merged.size()][]); } }3.4 核心边界条件的检验清单我在刷这道题时给自己列过一个边界测试清单每次写完代码都会挨个过一遍不建议跳步。intervals []应该返回[]不能报数组越界。intervals [[1,4]]只有单个区间返回原数组。intervals [[1,4],[2,3]]存在包含关系合并结果是[[1,4]]检验的是end取最大值还是直接覆盖。intervals [[1,4],[5,6]]恰好相邻但不重叠因为5 4合并结果应该是[[1,4],[5,6]]。intervals [[1,4],[4,5]]起点等于终点左闭右闭区间下有重叠结果是[[1,5]]。intervals [[1,4],[0,2],[3,5]]乱序输入排序后合并检验是否对原始无序数据有效。把这些用例自己跑一遍基本就能确定代码的正确性了。特别是第四种和第五种情况很多人在写重叠条件的时候会用cur[0] last[1]这里如果忽略了题目给出的区间是左闭右闭一旦相邻相等就判断为不重叠那结果就会出错。4. 实操中的常见问题与调试实录4.1 经典错因为什么用 max 而不是直接赋值遇到过不少同学在合并时写的是last[1] cur[1]而不是last[1] max(last[1], cur[1])。这种写法只在一种情况下正确就是新区间的终点比旧区间大一旦出现一个区间完全包裹另一个区间比如[[1,10],[2,3]]合并的终点应该是 10但错误写法会把它改成 3导致结果出错。为什么会有这种惯性思维因为很多人脑子里想象的重叠都是“两个区间部分交叉新的 end 肯定更大”。实际上区间之间存在三种位置关系完全不重叠、部分重叠、完全覆盖。部分重叠时更新为更大的 end完全覆盖时旧区间 end 本来就更大不能缩小。这个知识点我用一句话总结了合并区间的 end只可能变大或不变绝无可能变小。掌握了这个规律写max就是必然选择而不是背写法。4.2 经典错因开区间/闭区间混淆引发的边界灾难很多题解会告诉你判断条件是cur[0] last[1]但推导过程里用的是开区间或半开半闭的讨论跟题目本身不完全一致。你要是只听结论不看区间定义很可能在相邻区间[[1,4],[4,5]]上栽跟头。在左闭右闭区间模型里[1,4]和[4,5]在数字 4 处相交所以它们必须合并成[1,5]。如果错误地使用cur[0] last[1]作为重叠条件就会认为它们不重叠最终输出错误答案。反过来在会议室问题中因为会议结束时间和下一场开始时间通常不共享判断条件可能不同这要具体题目具体分析。所以刷题时第一步永远要先看清楚区间开闭定义别想当然套模板。4.3 关于“原地修改”和返回结构的困惑我在代码交流区经常看到有人问我不开新的 merged 列表直接修改原数组行不行理论上当然可以比如排完序后使用一个指针 idx 指向当前已合并区间的末尾遍历时不断原地更新intervals[idx]最后只返回前 idx1 个区间。但这样做会留下一个脏数据区域如果用 Python 切片可以轻松截断但在 C 或 Java 里需要额外处理数组长度。个人建议除非面试官明确要求 O(1) 额外空间或者不允许开辟新结构否则没必要做这种优化。merged列表在整个算法过程中是必要的——因为它承担了“动态维护最后一个区间终点”的功能。用空间换代码清晰度在这种题目里完全划算面试官不会因为你多开一个结果数组就扣分。4.4 性能与代码风格的细节建议虽然这道题核心是排序加扫描但在代码性能上仍有一些值得打磨的地方在 Python 里intervals.sort()用的是 TimSort对基本有序的数组非常快所以先别自己写排序函数标准库性能更好。Java 里如果担心a[0] - b[0]溢出可以用Integer.compare(a[0], b[0])这道题区间范围一般到不了溢出边界但这是个好习惯。遍历时建议使用基于索引的循环而不是创建子数组切片比如不要写for cur in intervals[1:]:因为切片会额外拷贝一份列表增加空间开销直接用for i in range(1, len(intervals))更规范。当然实际上对于时间要求不苛刻的 LeetCode 题目差别不大但面试中主动提到这个点能加分。注意热题100里的很多题目通不过往往不是算法有问题而是代码风格和边界没处理好。学会在写完代码后主动说明“这段代码的边界处理在哪里、为什么这么写”是面试官非常看重的工程素养。5. 从热题100看合并区间的变形与面试追问5.1 热题100里相关的区间类问题力扣热题100是一个面向面试的精选题库里面其实藏着多条和区间相关的暗线。合并区间这道题往前关联的是第57题插入区间往后关联的是第252题会议室、第253题会议室 II、第435题无重叠区间以及第452题用最少数量的箭引爆气球。插入区间和合并区间的关系非常紧密给你一个已经按起点排好序且不重叠的区间列表再插入一个新区间要求最后依然有序且不重叠。解法就是一个变形的合并流程核心逻辑依然是“找重叠区间、合并终点取最大”。你要是能先把合并区间吃透插入区间基本就是多了一个二分查找定位插入位置的步骤代码思路几乎一样。无重叠区间则反过来了给定一堆区间问至少要移除多少个区间才能让剩下的区间互不重叠。它的贪心策略是“按终点排序每次保留终点最小的区间”本质上也是区间覆盖问题的标准解法。这些题放在一起刷你会发现自己对区间重叠模型的理解会快速上一个台阶。5.2 面试官常见的追问与应对思路面试官在合并区间之后特别喜欢追问几个变种建议提前做好准备。第一个追问如果输入的区间有很多而且不是一次性给你而是以数据流的形式到达怎么处理这是一个在线算法问题。因为你无法预知未来区间预处理排序就失效了通常需要我们按到达顺序用有序结构动态插入比如平衡树。每次插入新区间时找和它有重叠关系的前驱与后继区间进行合并整体复杂度是 O(log n) 每次插入。这个追问考的是对排序预处理不可用的敏感度。第二个追问如果区间是字符区间或者泛型区间而不只是数字区间能不能用同样的思路其实只要区间端点定义了全序关系按起点排序、终点取更大的思路依然成立只是你没法直接用数组下标做比较需要抽象出 Comparable 方法。这个追问往往是想考代码设计的抽象能力。第三个追问如果区间存在嵌套关系例如多个区间都包含同一个小区间你如何保证合并结果不遗漏也不过度合并这就是回到算法自身正确性的证明上。你可以用数学归纳法按步推演也可以画图把区间的排序后关系可视化。能把这个讲清楚的人基本上说明是真正理解了这道题。5.3 合并区间在真实业务场景的映射聊完面试我再说点实际的。合并区间并不只是刷题专用它在真实业务里的映射非常广。最典型的是日程安排与会议管理给定一批会议的起始时间我们要合并出所有忙碌时间段看哪些时段是空闲的。再比如在线广告投放系统的排期管理多个订单可能覆盖同一时间段的广告位系统需要把重叠的投放计划合并成一条记录用于库存扣减和计费。去年我在处理一个用户活跃时段统计的需求时就把用户的登录日志按日期时间粒度切割成区间然后需要对不同来源的登录记录做一次区间合并才能算出每个用户单日在线时间的真实覆盖范围。当时用的就是先排序、再线性扫描合并的套路虽然是业务代码而不是算法题但核心逻辑完全一致。所以说合并区间的思维确实能直接迁移到工程实践里这也是这类题能常驻热题100的重要原因。6. 备考点拨如何把这道题在面试中讲到加分6.1 讲思路的仪式感比炫技更重要面试写算法题时最忌讳拿过来就写。就算你已经见过这道题也建议按“理解题目、澄清边界、提出思路、写代码、验证用例”的节奏来表现。对合并区间这道题我建议的叙述思路是这样的先跟面试官确认区间是左闭右闭然后分析暴力求解的复杂度再说“如果先把区间按起点排序重叠判断只在相邻区间之间进行就能用一次扫描完成合并。于是整个算法的瓶颈落在排序上总体复杂度 O(n log n)”。这种结构清楚、从问题出发推导解决路径的表达方式比直接喊一句“用贪心”要有说服力得多。6.2 代码写完后要主动自查什么写完代码不要干等面试官发问主动拿例子过一遍是加分的表现。我会用题目自带的案例走一遍排序后变成[[1,3],[2,6],[8,10],[15,18]]扫描到 [2,6] 时发现 2 小于等于 3更新终点为 6扫描到 [8,10] 时发现 8 大于 6新增区间扫描到 [15,18] 时发现 15 大于 10新增区间最后得到正确结果。走完例子后我还会特意提一个“易错点自查”不会出现终点变小的情况因为每次合并都用max更新不会漏掉最右侧的区间因为循环结束后 original 的最后一个区间要么被合并进结果要么以独立区间入结果。这两点放到面试里说会证明你有良好的算法敏感度。6.3 给复习节奏的一点个人建议刷题这事儿我自己的体验是不要追求刷完多少题而是要追求把一类题真正吃透。合并区间作为一个经典代表应该进入你的“二刷重点清单”。第一遍刷的时候可能只求 AC第二遍建议你自己给自己讲一遍思路能不能卡住不查资料写出来第三遍再用它去串相邻的区间问题尝试一题多解。这道题选进热题100不是偶然——它难度适中既能筛选出完全没有区间概念的新手也能通过追问区分出只会背模板和真正理解贪心的人。如果你能把这道题讲透热题100里面很多题目你都会觉得轻松一些。我自己的体会是区间题最重要的不是记住某种固定写法而是培养一种条件反射看到区间问题先问自己能不能排序排序以后能不能简化重叠条件如果答案是可以就果断排序。这种直觉一旦建立起来你会发现自己解很多区间相关题目的速度都会快起来。希望这篇内容能帮你在合并区间这道题上节省一些摸索时间后面刷插入区间、会议室这些题你会明显感觉顺手很多。