1. 先说结论这道题到底在考什么“合并区间”几乎是面试手撕代码环节的标配题目。我刷了几百道题之后回头看这道题之所以被反复拿出来考不是因为它难而是因为它能在一道题里同时考察三样东西排序思维、边界处理和代码实现能力。这三样恰恰是日常业务开发中最常用到的底层能力尤其是处理时间段、IP段、版本号段这类数据时合并逻辑简直无处不在。先给没做过的朋友一句话说清楚题目给定一组区间比如[1,3]和[2,6]因为2小于等于3两者有重叠合并成[1,6]如果完全不相交比如[1,2]和[3,4]就保持原样。最终返回一个没有重叠区间的列表。这道题适合谁来参考如果你是准备大厂面试的应届生或者工作几年想跳槽、想补算法短板的在职开发再或者只是单纯想巩固一下排序和数组操作的基础这篇内容都能直接用。我会把从读题到写代码、再到面试现场如何讲清楚思路的完整过程拆开揉碎讲一遍让你不光会写还能讲得头头是道。2. 为什么几乎所有解法都要先排序2.1 不排序的直观感受乱成一团我第一次做这道题的时候第一反应是“那我遍历一遍看到重叠就合并不就行了”。结果代码写到一半就发现不对劲[2,6]和[1,3]这种顺序颠倒的情况遍历到[2,6]时根本不知道前面还有个[1,3]在后面等着得回头反复扫描复杂度蹭蹭往上涨。更麻烦的是合并完一个新的大区间之后这个新区间可能又跟后面的某些区间重叠你要反复验证。打个比方你有一堆时间安排今天下午三点开会、上午十点开会、明天早上九点开会如果你不按时间排序就硬着头皮去合并重叠时段必然要来回翻日历。排序的作用就是让所有区间按起点从小到大排好队这样你只需要从左往右扫一遍判断相邻区间是否重叠就够了不需要回头。2.2 排序到底排什么排序的关键字是区间的起点也就是每个区间的第一个值。起点相同的情况下理论上按终点排也行但大多数场景下起点排序已经够用。实现上Python 里直接intervals.sort(keylambda x: x[0])Java 里用Arrays.sort(intervals, (a, b) - a[0] - b[0])C 里用sort(intervals.begin(), intervals.end())默认就会按第一个元素排。这里有个小坑Java 里a[0] - b[0]如果差值特别大可能溢出但区间题目一般数值不会那么极端稳妥起见也可以用Integer.compare。排序的时间复杂度是O(n log n)这决定了整个算法的上限。也就是说无论你合并过程写得多快整个算法的时间复杂度都不可能低于O(n log n)因为排序就是瓶颈。明白这一点后面跟面试官聊优化空间时就能有的放矢合并过程本身就是O(n)整体复杂度已经最优。3. 核心思路一次遍历完成合并3.1 合并的本质是“扩展边界”排序之后核心逻辑其实特别简单维护一个“当前合并区间”然后依次往后扫描。每看到一个新区间就问一个问题——新区间的起点是否小于等于当前合并区间的终点。如果是说明两者重叠合并方式就是把当前区间的终点更新为两者终点中的较大值如果不是说明新区间和当前合并区间已经彻底分开了那就把当前合并区间存入结果集然后让当前合并区间指向这个新区间。这里有一个初学者很容易绕进去的点为什么要取终点较大的那个而不是直接用新区间的终点因为合并的本质是求两个区间的并集并集的范围要从最小的起点延伸到最大的终点。比如[1,4]和[2,5]合并后是[1,5]终点取的是5而不是4但如果后面来的是[2,3]终点就仍然是4因为[2,3]整个被[1,4]包住了。3.2 边界情况小于、等于和包含重叠的判断条件是新区间起点 当前区间终点。注意这里的等号很多人在面试时容易忽略这个细节导致[1,2]和[2,3]这种首尾相接的情况没有被合并。题目里通常会说“如果两个区间有交集则合并”而[1,2]和[2,3]在数学上交集是{2}不是空集所以是应该合并的。万一题目明确说“首尾相接不合并”你只需要把等号去掉就行。还有一种情况是包含关系比如[1,10]和[2,3]。这时候新区间的终点3小于当前区间的终点10如果你直接用新区间的终点去更新反而会把大的区间缩小这是绝对错误的。所以更新终点时一定要取Math.max或者max()不能直接赋值。3.3 用一个例子模拟完整流程拿[[1,3], [2,6], [8,10], [15,18]]来说排完序后原样就是[[1,3], [2,6], [8,10], [15,18]]初始化当前合并区间为[1,3]扫描到[2,6]2 3重叠合并为[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]]这里最后一步特别容易漏循环结束后当前合并区间还没有被存入结果集因为它是等到“遇到不重叠区间”才被存进去的。如果遍历结束了还没遇到不重叠的区间它就一直在手里攥着。所以你必须在循环外面再补一次添加操作。这个细节几乎是每场面试必问的写完代码主动提一句“最后那个区间别忘加进去”面试官会对你印象加分。4. 代码实现三种主流语言一次给全4.1 Python 实现def merge(intervals): if not intervals: return [] intervals.sort(keylambda 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这个写法跟前面讲的“维护当前合并区间”有点区别它直接把结果集的最后一个元素当作当前合并区间代码更短也更 Pythonic。核心逻辑完全一致interval[0] res[-1][1]表示不重叠直接添加否则就合并更新右端点。4.2 Java 实现public int[][] merge(int[][] intervals) { if (intervals.length 0) { return new int[0][2]; } Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] res new ArrayList(); for (int[] interval : intervals) { if (res.isEmpty() || interval[0] res.get(res.size() - 1)[1]) { res.add(interval); } else { res.get(res.size() - 1)[1] Math.max(res.get(res.size() - 1)[1], interval[1]); } } return res.toArray(new int[res.size()][]); }Java 版本需要注意res.toArray的写法new int[res.size()][]是固定套路如果你写new int[0][]也可以但有些面试官可能会问区别简单说就是前者预分配了大小后者靠反射动态扩容后者在 Java 官方文档里其实是推荐写法因为不影响性能而且更简洁。4.3 C 实现vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint res; for (auto interval : intervals) { if (res.empty() || interval[0] res.back()[1]) { res.push_back(interval); } else { res.back()[1] max(res.back()[1], interval[1]); } } return res; }C 的sort默认对vectorvectorint排序时会按照字典序比较也就是先比第一个元素如果第一个元素相同再比第二个。对于这道题我们只需要按第一个元素排但默认行为也不会有问题因为第二个元素的大小不影响合并结果起点相同的区间谁先谁后都无所谓合并后终点取最大值就对了。4.4 三种实现的小对比语言核心API注意事项Pythonlist.sort(keylambda x: x[0])直接在原列表上排序节省空间JavaArrays.sort(intervals, (a,b) - a[0]-b[0])注意比较器溢出可用Integer.compareCsort(intervals.begin(), intervals.end())默认字典序排序本题完全够用5. 面试现场如何从思路讲到代码让面试官点头5.1 不要上来就写先讲清楚三个关键决策面试官看重的不是你会不会背代码而是你能不能把决策过程讲明白。我建议你在写代码之前先用两分钟把三个关键点说清楚第一为什么要排序。因为排序可以让区间按起点有序排列使得我们只需要关注相邻区间的关系不需要反复回头扫描将问题从可能的多重嵌套简化为单次遍历。第二重叠条件如何判断。当前区间的起点小于等于上一个合并区间的终点就说明有交集或首尾相接。这里主动提一句“不同的题目定义可能不同如果需要严格分离就改成小于号”表明你考虑过边界条件的变体。第三合并时如何更新终点。不能简单覆盖而是取两个终点之间的最大值防止包含关系下把大区间错误缩小。这三句话说完面试官基本已经认可你的思路了。你还没写一行代码但得分点已经拿了一半。5.2 写完代码之后的三个加分动作代码都写完之后别急着说“写完了”主动做三件事第一主动提边界条件。问面试官“如果输入是空数组怎么办”然后在代码里体现出来——最前面加上判空逻辑。有些面试者会忘记这个但实际工作中你根本无法保证上游数据非空这是工程素养的体现。第二主动跑一个例子。用手里的例子或者用[[1,4], [4,5]]这种首尾相接的情况把循环过程一步步演算给面试官看。这能证明你的代码不是背的是真正理解逻辑的。第三主动说复杂度。排序是O(n log n)遍历是O(n)总体是O(n log n)空间方面如果排序原地进行额外空间只有结果集最坏情况是O(n)。把复杂度讲清楚说明你对自己的代码有完整的性能认知。5.3 常见的追问和应对思路面试官很可能会顺势追问几个变体问题这里提前给你备好答案追问一“如果区间里放的是字符串怎么办”比如 IP 段合并[“192.168.0.1”, “192.168.0.10”]这种。核心思路不变但比较大小不能直接比字符串需要先把 IP 转换为整数。每个 IP 拆成四段每段占 8 位拼成一个 32 位整数再比较。这种题看起来是算法题其实是考察你能否把业务数据映射为算法可处理的结构。追问二“如果合并的是时间段怎么办”比如会议室的预订时间、直播的在线时段。时间可以用时间戳转成整数然后套同样的合并逻辑最后再把结果转回可读时间格式。这种题目在真实业务里极其常见我后面会展开讲一个具体案例。追问三“能不能用扫描线思路解”可以的。把每个区间拆成左端点和右端点两个事件左端点 1右端点 -1然后对所有事件点按位置排序遍历时累计覆盖次数当覆盖次数从 0 变成 1 时记录起点从 1 变成 0 时记录终点。扫描线解法的时间复杂度同样是O(n log n)但代码更复杂一般不是为了秀技巧不建议主动写除非面试官点名要。6. 进阶视角从“会写”到“会用”6.1 真实业务场景之一时间段合并我在实际项目中做得最多的合并区间就是处理用户在线时长统计。假设我们埋点采集到用户一段时间的登录记录[09:00, 10:30]、[09:40, 11:00]、[14:00, 15:00]。如果直接把这些时间段加起来得到总时长就会把09:00到10:30和09:40到11:00的重叠部分重复计算导致统计虚高。先用合并区间逻辑把时间段合并成[09:00, 11:00]和[14:00, 15:00]再计算总时长结果就准确了。这种场景里的一个小坑是时区的处理。如果用2024-01-01 09:00:00这种字符串格式直接比较字符串排序在某些情况下可行但一旦涉及跨天、跨月、跨年字符串排序就会出错因为“2024-01-31”和“2024-02-01”之间字符串比较没问题但“2024-1-2”和“2024-10-1”这种不规范的格式就会出问题。所以工程上一定要先统一转成时间戳或标准格式再排序合并。踩过一次坑之后我的习惯是任何时间区间合并第一步永远先转时间戳。6.2 真实业务场景之二IP 段合并另一个高频场景是 IP 黑名单合并。安全系统每天会收集大量恶意 IP 段比如[192.168.0.1, 192.168.0.255]、[192.168.0.100, 192.168.1.50]这些段之间有大量重叠。如果每条规则单独匹配效率很低而且规则数量一多维护和排查都很痛苦。用合并区间把重叠的 IP 段合并成若干个互不相交的大段匹配的时候直接用二分查找定位 IP 落在哪个段里性能可以从O(n)降到O(log n)。具体实现时把 IP 转成 32 位整数a.b.c.d转为a * 256^3 b * 256^2 c * 256 d。然后对这些整数区间做合并最后再把结果转回点分十进制格式。这里有一个容易踩的坑如果直接用字符串排序192.168.1.100和192.168.1.50的字符串顺序是错的因为“100”排在“50”前面。必须转整数这是这类题真正的工程门槛。6.3 真实业务场景之三版本号段合并还有一个比较隐蔽的场景是版本范围合并。比如某些功能只在特定版本区间内可用[1.2.3, 1.4.0]、[1.3.0, 2.0.0]需要合并成[1.2.3, 2.0.0]来给用户做兼容性判断。版本号不能直接按字符串排序因为“1.10.0”会排在“1.9.0”前面。正确的做法是把版本号按.拆成数组逐位比较或者直接转成一个足够大的整数。比如1.2.3可以转成1 * 10000 2 * 100 3前提是约定每段不超过 99真实场景中这个约定通常可行但更稳妥的写法还是逐位比较。6.4 发散思考区间树和更多可能如果你对区间类问题特别感兴趣还可以继续研究区间树Interval Tree和线段树。合并区间本质上处理的是静态的、一次性给出的区间集合但如果数据是动态增长的——比如实时往集合里插入新的区间同时需要快速查询当前被覆盖的范围——那合并区间这个思路每次都要重新排序效率就不够了。这时候可以用区间树插入和查询都是O(log n)。不过面试中能写出合并区间已经足够区间树更多是竞赛和高级系统设计才会用到我建议你先把基础吃透有余力再深入。7. 常见 Bug 与排查技巧全是实操中真实踩过的坑7.1 忘加最后一个区间前面已经提过这是最高频的 Bug。排查方法很简单检查循环结束后是否把当前合并区间手动添加到结果集。一个行之有效的记忆技巧是把“当前合并区间”想象成手里拿着的一件物品只有遇到下一个装不下的东西时才放下遍历结束你手里还有东西必须主动放下。用这种具象化思维基本不会再忘。7.2 直接用新区间终点覆盖旧终点初学者最容易犯的错。[1,10]和[2,3]合并后变成[1,3]把大区间缩小了数据直接错误。这类问题的特征是结果区间比预期要短。排查时只要记住一个原则合并区间是取并集而并集的右端点永远是所有重叠区间中右端点最大的那个必须用max比较。7.3 排序遗漏或排序关键字错误有几个场景会导致排序出问题一是忘写排序直接对原始数据遍历结果完全不可控二是按终点而不是按起点排序合并逻辑立刻失效三是自定义比较器写错比如 Java 里忘写返回值为-1、0、1的完整逻辑只写了a[0] - b[0]极端情况下可能溢出。排查时先确认数据有序再排查其他逻辑能省很多时间。7.4 区间定义是左闭右开还是左闭右闭这是区间类问题最隐蔽的陷阱。有些题目定义区间是[start, end]两端都包含有些题目定义是[start, end)右端不包含。如果是左闭右开那[1,2)和[2,3)其实是不重叠的因为第一个区间只包含1第二个只包含2和之后的值两者没有公共元素但如果是左闭右闭那[1,2]和[2,3]重叠点在2需要合并。你做这道题之前一定要先和面试官确认清楚区间的定义不同定义下代码里重叠判断的等号要相应调整。7.5 输入数据本身乱序且区间数量极大如果区间数量达到百万级直接用List存结果也可以但频繁的扩容操作会带来额外开销。更优的做法是预先算出最终结果的数量再一次性分配空间或者直接用链表存储后转数组。不过这些属于优化细节面试阶段先保证正确性后续再提优化方案反而显得你有工程全局观。7.6 快速自查清单排查点检查方法典型症状排序是否完成打印排序后的输入合并结果乱序、缺项是否忘加最后一个区间检查循环外是否有 append结果少一个区间是否错误覆盖终点检查合并分支是否用 max合并后区间变短区间开闭定义确认题目或面试官说明边界值合并错误空输入处理检查是否有判空逻辑空数组报错或返回错误8. 从这道题延伸出去算法题到底怎么刷才有效8.1 一道题吃透比刷十道题有用我发现很多人在刷题时有一个误区追求数量每天刷十几道每道题看一遍思路就过了结果面试时碰到原题也写不出来。合并区间这道题我建议你至少做三遍第一遍看题后自己尝试 30 分钟能写多少写多少第二遍对照标准答案把思路理顺用自己的话把三个决策点讲出来第三遍隔一周再不看答案写一遍确保真正内化。三遍做完这道题的收获比盲目刷十道题更大。8.2 同类题目的横向对比合并区间不是孤立的一道题它和几个相近题目可以放在一起横向对比插入区间给定一组已经合并好的无重叠区间再插入一个新区间并保持合并后的状态。核心思路是从左往右找到插入位置处理三种情况完全在左、完全在右、部分重叠。会议室 I判断一组区间是否能安排在同一天本质是判断是否存在重叠。排序后检查相邻区间是否有交集。会议室 II计算最少需要几个会议室本质是求区间重叠的最大深度。除了排序后暴力统计还可以用最小堆维护当前正在进行的会议。删除被覆盖区间删除所有被其他区间完全覆盖的区间返回剩余数量。排序规则需要特别设计起点升序终点降序然后依次比较。这些题目共享同一套排序 线性扫描的思维框架刷一道等于刷四道。如果能做到“举一隅而以三隅反”面试官问变体题时你也能从容应对。8.3 做题要做的三层思考第一层是题目本身能写出正确代码。第二层是复杂度分析能讲清楚时间、空间复杂度及原因。第三层是业务映射能在面试官追问“这道题有什么实际场景”时快速举出时间段合并、IP 段合并、版本号段合并等例子。做到第三层的人非常少但一旦做到面试官对你的评价会显著提升。9. 面试之外这道题带给我的三点心得9.1 排序是很多问题的突破口合并区间最核心的一步就是排序。我后来发现大量看似复杂的问题只要先把数据排序立刻就变简单了。比如合并重叠子串、计算最大重叠天数、求最少的箭射爆所有气球全都是排序后线性扫描解决。遇到一个新题觉得无从下手时不妨先问问自己如果数据有序这个问题会不会变简单如果是排序大概率就是你的第一步。9.2 边界条件是最容易丢分也最容易得分的地方算法题真正拉开差距的往往不在主流程而在边界条件。合并区间的边界条件包括空输入、单元素区间、首尾相接、完全包含、最后一个区间。每道题做完后建议你把所有能想到的边界条件列出来逐一验证代码是否正确。这个过程不仅能帮你拿下面试中的隐藏得分点也能培养工程上严谨的思维习惯。毕竟在实际项目中90% 的线上事故都发生在异常输入和边界条件上。9.3 面试时“讲题”和“做题”同等重要很多人技术能力不差败在不会表达。面试官问你思路时不要闷头写代码要边写边讲。讲什么讲你的思考过程、你的取舍逻辑、你注意到的边界条件。你会发现讲着讲着思路反而更清晰代码也写得更顺畅。合并区间这道题如果你能按我前面说的“三个关键决策 循环外添加最后区间 复杂度分析”这个节奏来讲大概率会被面试官认为是一道“满分回答”。这种能力是可以通过刻意练习获得的建议你在平时刷题时就把“口头讲题”当作练习的一部分。9.4 最后分享一个小技巧如果你在面试中写完了合并区间时间还富余可以主动跟面试官聊一句“这道题还可以用扫描线思路做把每个区间拆成事件点左端点加一右端点减一然后排序统计覆盖次数。两种做法时间复杂度一样但扫描线思路可以扩展处理区间覆盖面积、最大重叠深度等问题。”这段话一说出口面试官会觉得你不只是会背题而是对区间类问题有系统性理解。当然前提是你真的理解扫描线否则面试官深挖一问你就露馅了这个分寸要把握好。合并区间这道题说难不难说简单也不简单。它像一面镜子能照出你对排序的掌握、对边界的敏感、对复杂度的理解还有你现场沟通的节奏感。把这套思路吃透你收获的不只是一道题的解法而是解决一类区间问题的通用方法论。祝你在面试中遇到这道题时能写得从容、讲得漂亮。