合并区间这题我在面试里见过不下五十次说它是区间类算法题的“敲门砖”一点不夸张。题目本身看着特别简单——给出一组区间把互相重叠的合并成一个更大的区间最后返回不重叠的列表——但真正能一次写对的人我这些年筛下来不到三成。问题从来不在思路而在那些不起眼的边界条件和排序细节。这篇就把合并区间从头到尾拆开讲透包括核心解法、几个典型变体、面试现场最容易踩的坑准备算法面试的朋友可以把它当成一个最小闭环的专题来啃刷完这一篇区间类的题你就能应付大半。1. 这道题到底在问什么1.1 原题描述与真实业务场景为了方便不熟悉的朋友先用大白话描述一遍题目输入是一个二维数组每一行有两个整数代表一个区间的起点和终点比如[1,3]表示从1到3这个范围。可能存在多个区间彼此重叠比如[1,3]和[2,6]它们的交集就是[2,3]这一段合并之后应该得到[1,6]。要求输出的所有区间两两不重叠并且按起点升序排列。这个模型在真实工程里极其常见。最典型的是会议室预订系统一组会议室占用时间段如果时间有交叉管理员看到的不是一个密密麻麻的日程表而是一段段合并后的可用/占用区间。再比如日志采集系统服务器上报的日志往往带有时间段标签这些时间段经常错位重叠落地存储前需要合并成规整的时间片压缩存储体积、方便后续查询。还有数据库的连续ID范围合并、运营活动的时间线清洗本质都是同一套逻辑。所以面试官考这道题考的不只是你会不会背答案更是你有没有把底层模型抽象出来、应用到业务里的意识。1.2 面试官真正考察的能力很多候选人以为合并区间考的是“会不会写贪心”这是误解。这道题放在面试里真正的考察点至少有四个排序敏感度是否第一时间意识到无序区间无法高效处理需要先排序这体现的是“把问题化简为有序问题”的算法直觉。贪心策略的落地能力知道从左往右扫描、能合并就合并简单高效能否用几行代码说得清清楚楚。边界条件严谨性输入可能为空、只有一个区间、区间完全包含、端点恰好相等这些情况都要覆盖漏掉一个就是bug。代码表达与沟通能力你写出来的代码别人能不能一眼读懂遇到复杂情况你敢不敢和面试官确认“区间端点是否包含”这些都比单纯的解题速度更能反映真实工作状态。说白了这道题就是一个“人人都会做但很少人做得漂亮”的题目它把编码习惯和思维颗粒度暴露得很彻底。2. 核心思路与代码实现2.1 排序加贪心的核心逻辑合并区间的标准解法是“排序贪心”核心逻辑特别简单但每一步都要想清楚。第一步把区间按起点升序排序。排序的意义在于一旦区间按起点排列你从左往右扫描时后面区间的起点永远不小于前面区间的起点这样合并的判断就变成了“当前区间的起点是否落在上一个合并结果的终点之内”。不需要反复回头检查一次遍历就能解决。第二步维护一个结果列表先把第一个区间放进去作为“当前合并中的区间”接着逐个处理剩余区间如果当前区间的起点小于等于结果列表最后一个区间的终点说明二者有重叠则把最后一个区间的终点更新为两者终点的较大值否则说明当前区间和前面已经分割开了直接追加到结果列表尾部。整个过程只扫描一遍前面排序的O(n log n)是唯一的大头成本。这里有个关键细节容易忽略重叠的判断条件是用“当前区间起点累积结果的终点”比较但合并时终点要用“二者的最大值”。为什么是最大值因为存在完全包含的情况比如[1,10]和[2,3]起点2虽然小于终点10但终点不能更新成3必须保留更大的10否则就把区间缩短了。这个小细节很多人第一次写都会栽。2.2 多语言代码实现对比用Python写这个逻辑可以非常简洁def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) result [intervals[0]] for i in range(1, len(intervals)): if intervals[i][0] result[-1][1]: result[-1][1] max(result[-1][1], intervals[i][1]) else: result.append(intervals[i]) return result代码本身不到十行但每一行都有讲究。intervals.sort(keylambda x: x[0])显式指定排序键虽然Python对二维列表的默认排序也是先按首元素再按次元素但显式写出来更清晰也能避免某些语言默认行为不一致带来的隐患。result[-1][1]直接修改列表尾部元素的终点时间复杂度是O(1)完全可行。Java版本稍微啰嗦一点但思路一模一样public int[][] merge(int[][] intervals) { if (intervals.length 0) return new int[0][0]; Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] list new ArrayList(); list.add(intervals[0]); for (int i 1; i intervals.length; i) { int[] last list.get(list.size() - 1); if (intervals[i][0] last[1]) { last[1] Math.max(last[1], intervals[i][1]); } else { list.add(intervals[i]); } } return list.toArray(new int[list.size()][]); }注意Java里排序比较器我建议用Integer.compare(a[0], b[0])而不是a[0] - b[0]。后者在极端情况下可能产生整数溢出虽然面试场景很少考这个但写出来能让面试官觉得你基础扎实。JavaScript版也顺手给个var merge function(intervals) { if (intervals.length 0) return []; intervals.sort((a, b) a[0] - b[0]); const result [intervals[0]]; for (let i 1; i intervals.length; i) { if (intervals[i][0] result[result.length - 1][1]) { result[result.length - 1][1] Math.max(result[result.length - 1][1], intervals[i][1]); } else { result.push(intervals[i]); } } return result; };三种主流语言都跑得通实际面试时选自己最熟的那个就好面试官看重的是思路不是语言炫技。2.3 为什么这题必须排序我面试时就喜欢问一个问题不排序能不能做能但会很痛苦。假设区间无序你拿第一个区间去和后面所有区间比较合并出一个新的更大区间这个新区间可能又和之前已经处理过的某个区间重叠于是你需要反复回溯检查最坏情况下来回扫描复杂度退化成O(n²)甚至更高。更麻烦的是你很难证明“已经处理过的区间永远不会再被新合并结果影响”代码写出来极其绕。排序把这个混战变成了“流水线”所有区间的起点从左到右排列好你处理到某个位置时前面所有区间都已经定型只有最后一个区间还可能被当前区间扩展。这种“化无序为有序、化回变为单向”的思想不只在合并区间里出现后面讲到的几乎所有变体题都沿用了这个套路。所以排序不是可有可无的步骤它是整个解法的灵魂。3. 边界条件与细节陷阱3.1 判断重叠的三个关键分支写合并区间最容易翻车的地方就是重叠判断。展开来看两个区间的关系可以分成三种情况完全不相交、部分重叠、一个完全包含另一个。部分重叠时合并后的终点是两者终点的较大值完全包含时和部分重叠的处理方式其实一样都是取终点最大值完全不相交时直接追加新区间即可。所以用一行intervals[i][0] result[-1][1]加上一行max其实就把三种情况全收了。但还有一个很多人忽略的边界两个区间的端点恰好相等比如[1,3]和[3,5]。它们到底算不算重叠这取决于题目的区间定义是闭区间还是开区间。LeetCode默认是闭区间即端点包含所以[1,3]和[3,5]有公共点3应该合并成[1,5]。但如果在业务中你处理的是“时间区间左闭右开”那3这个时刻属于前一个区间还是后一个区间就需要和需求方确认。面试时遇到这种歧义主动问一句“端点是否包含”比闷头写代码高明得多。3.2 容易被忽视的输入情况空数组和只有一个元素的数组是防御式编程的第一道坎。空数组直接返回空列表只有一个元素直接返回原数组这两条guard clause能让你的代码在极端输入面前面不改色。很多候选人一上来就写循环体结果空数组直接下标越界当场社死。另一种情况是区间里包含负数比如[-5,-1]和[-3,2]。有人一看是负数就慌了其实排序和比较逻辑跟正数没有任何区别区间合并只关心大小关系不关心正负。还有单个点组成的区间比如[2,2]如果其他区间都不包含2它就应该保留在结果里作为一个独立区间这种case也容易漏。3.3 三种常见错误写法实录这里把我这些年面试中见到的经典bug整理成一张表每条背后都是一个真实的翻车现场错误类型错误示例后果忘了更新终点重叠时只append新区间输出结果仍有重叠区间用双端比较判断重叠nums[i][0] lst[-1][0] and nums[i][1] lst[-1][1]只处理了包含关系漏掉部分重叠排序后不处理首区间循环从0开始result初始为空第一个区间丢失或逻辑混乱第三点很多人会犯明明排序都写了但循环体里没想清楚初始状态。解法有两种要么像上面的代码一样先把第一个区间放进结果再开循环要么在循环里判断result为空或当前区间与结果末尾不相交时才追加。先放第一个区间再循环代码看起来最简洁我推荐这个写法。4. 复杂度分析与性能优化细节点4.1 时间复杂度是怎么算出来的合并区间的时间复杂度由排序和扫描两部分组成。排序阶段比较排序的通用下界是O(n log n)这也是整个算法的主导项扫描阶段每个区间最多处理一次是O(n)。总体时间复杂度O(n log n)。空间复杂度取决于排序的实现Java的Arrays.sort()对对象数组使用归并排序需要O(n)额外空间对基本类型数组使用双轴快速排序则只需要O(log n)栈空间Python的list.sort()是Timsort最坏情况O(n)额外空间。如果只算算法本身维护结果列表的空间则是O(n)。面试时能把这个空间细节讲清楚会显得你对你使用的语言底层很熟。4.2 输入有序时能否做到O(n)很多候选人没想过一个问题如果输入本身就按起点排好序了合并区间可以做到O(n)。扫描逻辑不变排序直接跳过即可。这在真实业务中很常见比如数据库查询结果往往自带排序或者上游系统已经按时间字段排过序了。所以拿到题目先问一句“输入是否有序”不是废话而是能帮你省去整个排序开销的加分项。更极端的情况是区间端点的取值范围有限比如已知所有端点在1到10000之间可以用桶排序或计数排序把排序成本降为O(n K)K是端点取值范围这样整体就是线性时间。但这种方案在面试里提出来会让人觉得你有点炫技除非题意明显暗示端点范围很小否则不建议主动往这个方向编。4.3 原地合并与副本操作的选择合并区间有原地修改和新建结果数组两种风格。原地修改的意思是在原数组上直接改把合并后的区间往前挪最后返回前k个元素。这样能省一点空间但代码可读性差而且面试场景下容易把自己绕晕。我个人的习惯是“宁可多开一个结果数组也要保持代码一眼能看懂”。毕竟面试不是生产环境展示清晰的思路比展示极致的空间压缩更值钱。如果你在公司里真的面临内存紧张的问题再去优化成双指针原地覆盖也不迟——那又是另一种乐趣了。5. 面试中常考的四类变体5.1 插入区间先插入再合并插入区间是合并区间的直接变种给定一个已经按起点排好序且互不重叠的区间列表再插入一个新区间返回合并后仍然有序且不重叠的结果。最自然的解法是把新区间追加到列表尾部然后调用一次合并区间逻辑整体O(n log n)更优的做法是三步走收集所有与新插入区间完全不相交的左侧区间合并所有与新区间重叠的区间再收集右侧区间。三步走是O(n)而且能把“合并”这个过程拆解得非常清晰面试官很容易跟上你的思路。推荐两种方案都提一下先讲O(n)的三步走再补一句“如果允许排序也可以直接复用合并区间”。5.2 会议室问题合并区间的孪生兄弟会议室问题是合并区间最经典的变体问题描述是这样的给定一个会议时间区间列表问至少需要多少个会议室才能容纳所有会议本质是求所有区间在任意时刻的最大重叠数量。解法一可以用扫描线每个会议开始时间1、结束时间-1做一个差分数组从左到右累加过程中的最大值就是答案。解法二用优先队列按开始时间排序后用一个小根堆维护当前正在进行的会议的结束时间遇到新会议就弹出已经结束的堆顶然后压入新会议堆的大小就是当前并发数最大值即答案。这题和合并区间共用一套“按起点排序”的思维但目标从“合并重叠”变成了“统计重叠峰值”非常有区分度。5.3 区间交集与删除被覆盖区间区间交集问题给两个已经各自有序且不重叠的区间列表求它们的交集。核心是双指针两个列表各取一个区间交集存在的基本条件是max(start1, start2) min(end1, end2)交集的起点是较大起点终点是较小终点然后谁的终点小谁的指针向后移动。这个解法只用一遍双指针O(m n)写起来非常爽。删除被覆盖区间则是另一个方向给定区间列表删除所有被其他区间完全覆盖的区间返回剩余数量。解法是先按起点升序、相同起点按终点降序排列目的是保证覆盖率判断是单向的。遍历时维护一个“当前全局最大终点”如果某个区间的终点不超过它说明被覆盖计数加一否则更新全局最大终点并保留该区间。5.4 变体之间的共性思维把四类变体放在一起看不难发现它们都逃不出“排序 单次扫描 维护一个关键状态”的框架。合并区间维护的是“当前合并结果的最大终点”会议室维护的是“当前并发堆”区间交集维护的是“双指针的移动条件”删除覆盖维护的是“全局最大终点”。面试时如果被连续追问变体题只要抓住这个框架就不会慌。你能从一道题延伸到一族题本身就是远超“会做一题”的加分信号。6. 避坑指南与实战心得6.1 面试现场的交流策略合并区间这道题我建议拿到题目先花三十秒说清楚三件事一是确认区间端点是否包含默认闭区间二是确认输入是否已经排序能不能自己排序三是确认返回值的要求是按起点升序还是保持原序。这三个确认做完再动手写代码面试官会立刻觉得你是一个有工程协作意识的候选人而不是一个闷头刷题的工具人。写的过程里每写完一个关键步骤就口头解释一句“这里排序是为了……”“这里取最大值是因为……”让面试官全程跟得上你的思路。6.2 编码层面的好习惯三个小习惯能救你很多次第一intervals.sort(keylambda x: x[0])比intervals.sort()更明确不会依赖语言默认行为第二循环从1开始并先把首个区间放入结果能天然处理单元素输入第三重叠判断用而不是因为闭区间下端点重合也算重叠。这几个细节写对了你的代码在边界上就是稳的。我见过太多候选人思路全对就挂在写成了这种错误比不会做更可惜。6.3 刷题之外的一点延伸我个人的体会是合并区间这题值得当作“模板题”反复默写不是为了背代码而是把“排序后单趟扫描”这个套路内化成自己的直觉。它管用的范围远超区间合并本身——字符串去重、链表合并、日程冲突检测很多看似不同的场景底层都是这个模型。面试前花一个晚上把这一题和那四个变体全部手写一遍比盲目刷二十道难题有用得多。等你在白板上能把合并区间写得又快又稳你会发现在后续遇到类似的区间问题时整个人都会从容很多。