企业官网建设流程全解析

在算法面试的各类题单里，“合并区间”属于那种“看起来闭着眼都能写，真写起来十个人七个错”的题。说它不难，是因为解法思路很直白——排序、遍历、合并；说它阴险，是因为重叠边界、引用修改、排序稳定性这些细节，每一个都能让你在面试现场卡壳。我见过不少候选人，聊到这道题时能背出代码框架，但让他解释为什么合并时要取max(end)，或者追问一句“和插入区间有什么不同”，就开始含糊了。

这篇文章默认读者已经会用某种语言写循环，但不需要背过这道题。我会从最朴素的思路开始拆，再到手写代码、边界测试、面试追问，最后聊一聊怎么把这一道题吃成“区间家族”的一整串。如果你正在准备面试，或者刚刚开始刷题不久，这篇日记应该能帮你少踩几个我当年踩过的坑。

1. 先从题目本身说起：合并区间到底在考什么

1.1 原题长什么样

输入是一个二维数组，每个元素表示一个闭区间，第一项是左端点 start，第二项是右端点 end。要求输出一个新的二维数组，把所有有重叠的区间合并成一个区间，按顺序返回。

举个例子：

输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] 输出：[[1, 6], [8, 10], [15, 18]]

因为[1, 3]和[2, 6]有重叠，合并成[1, 6]；[8, 10]和谁都不重叠，原样保留；[15, 18]同理。

再给一个容易让人迷惑的例子：

输入：intervals = [[1, 4], [4, 5]] 输出：[[1, 5]]

注意这里[1, 4]的右端点和[4, 5]的左端点都是 4，在闭区间的定义下它们“接触”了，也算重叠，需要合并。这个细节很多第一次写的人会漏掉。

1.2 这道题考的不是“算法”，而是“是否想清楚”

我最初刷到这道题时，觉得它毫无技术含量，不就是排序加两个指针吗？直到我在一次模拟面试里写了十五分钟，最后跑测试用例挂在了空数组和边界重叠上，才意识到这题一点都不简单。

它真正考的东西有几层：

• 是否知道排序是处理区间问题的基础手段，以及为什么排序能让问题降维；
• 能不能准确处理“重叠”的数学定义，而不是靠感觉；
• 合并时的边界更新是不是真的考虑到所有情况；
• 代码写出来是不是结构清晰、无副作用，而不是在一个临时列表上反复插入删除。

换句话说，这道题是一道“基本功体检题”，它不考偏门算法，却能从代码风格和边界意识上看出一个人的工程素养。这也是为什么那么多公司的面试题库里都有它，而且往往是被放在第一轮的手写代码环节。

2. 合并的核心套路：排序 + 贪心扫描

2.1 为什么必须先排序

如果输入区间完全无序，让你手工合并你会怎么做？大概会拿起第一个区间，然后遍历剩下的所有区间找重叠，找到后更新边界，再继续。这种做法的问题在于，你每合并一个新区间，它可能又跟之前已经处理过的区间产生新的重叠，于是你得回溯。最坏情况下时间复杂度能到 O(n²)，而且代码写起来非常拧巴。

排序的价值在于：把二维的“谁跟谁重叠”问题，降维成“当前区间和已合并区间”的线性问题。

按左端点升序排序之后，区间的顺序是固定的。此时如果后一个区间的左端点大于前一个区间的右端点，那么再见，两者不可能重叠，因为后面所有区间的左端点只会更大，更不可能跟前面重叠。这个性质让“合并”变成一个纯粹的从左往右扫描过程，每一步只需要跟当前维护的最后一个合并区间比较即可。

可以类比整理日程表：如果会议时间是乱的，你得来回核对；把会议按开始时间排好序，你只需要顺着看一遍，就能把所有连着的会议拼成一段。

2.2 三种重叠关系，用一条判断条件覆盖

很多人写这道题时会去分类讨论“包含”“相交”“相连”，然后每种情况写一个分支。其实不用。只要排好序，所有情况都可以归纳成一种判断：

• 当前区间的左端点start <= 已合并区间右端点 end，说明重叠，需要合并。

在这个条件成立时，不需要去想到底是包含还是相交，只需要把合并后区间的右端点更新为max(上一次的end, 当前区间的end)。因为合并区间的左端点一定取上一次的左端点（排序后它最小），唯一要变的只有右端点。

举个例子：

• [1, 5]和[2, 3]：嵌套关系，右端点应该保持 5；
• [1, 3]和[2, 6]：相交关系，右端点应该变成 6；
• [1, 4]和[4, 5]：相邻相接，右端点应该变成 5。

三种情况，一条max(last[1], cur[1])全搞定。很多博客会把这个东西画成流程图，其实核心逻辑就是下面的代码结构：

result = [] for cur in intervals: if not result or cur[0] > result[-1][1]: result.append(cur) else: result[-1][1] = max(result[-1][1], cur[1])

代码总共四行核心逻辑，但这四行里有几个细节值得停下来想一想。

3. 手写代码：怎么做到一次写对、边界全过

3.1 一份足够稳的 Python 实现

先给出完整的实现，再逐段解释：

def merge(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # 如果 merged 为空，或者当前区间与上一个合并区间不重叠 if not merged or interval[0] > merged[-1][1]: merged.append(interval) else: # 重叠时，更新合并区间的右端点为较大值 merged[-1][1] = max(merged[-1][1], interval[1]) return merged

为什么这样写是稳的？

先说排序。sort(key=lambda x: x[0])确保只按左端点排序，右端点保持原顺序。对于左端点相同的区间，其实排序后谁在前谁在后不影响合并结果，因为它们在扫描时会从左端点相同的地方开始，逐一被合并进同一个区间，最终保留最大的右端点。

再说扫描。维护一个merged列表，其中最后一个元素就是我们正在“生长”的合并区间。每次取一个新的区间，只需要跟最后一个比。这个思路的直觉是：因为我们按左端点排序过了，所以重叠只会发生在“新区间左端点 <= 当前合并区间右端点”的时候，也就是说新来的区间只会“接”在最后一个合并区间后面，不可能回头跟更早的结果重叠。这是整个算法正确性的关键，面试时如果能主动说出这一点，观感会很不一样。

最后说更新。max(merged[-1][1], interval[1])考虑的是新区间右端点可能比当前合并区间大，也可能小。如果你不写max直接赋值merged[-1][1] = interval[1]，嵌套区间的情况就会出错。我见过很多次这种失误，包括我自己第一次手写时也犯过。

3.2 边界情况逐个测一遍

写代码最怕的是只测一个 Happy Path 就交卷。合并区间有几个边界一定要在面试时主动测：

• 空数组：返回空数组，不能访问下标。
• 单个区间：返回它本身。
• 全部重叠：比如[[1, 4], [2, 5], [3, 6]]，应该合并成一个[1, 6]。
• 全不重叠：比如[[1, 2], [3, 4], [5, 6]]，输出应该与输入一致。
• 相邻但不重叠：比如[[1, 2], [2, 3]]，因为闭区间端点相接，算重叠，输出[[1, 3]]。
• 区间嵌套：比如[[1, 10], [2, 3], [4, 5]]，别忘了最外面的右端点应该保持 10。

这些问题其实都可以靠几个简单的if分支解决，但前提是你想到了它们，并且在写代码之前就放进测试清单。

一个我在面试现场常用的技巧是：代码写完后不要马上说“我写好了”，而是顺手在注释里补充几个测试用例，然后模拟运行一遍。这个习惯能把面试官对你“思维是否缜密”的评分拉高不少。

3.3 为什么不要在原数组上原地修改

我第一次写这道题时，直接改了传入的intervals参数，因为想着能省内存。这在小规模测试里没问题，但有几个隐患：

• 排序已经是原地修改了，再在原数组上拼接、裁剪，很容易导致索引混乱；
• 某些编程语言中函数参数是引用传递，修改会影响调用方，在面试场景下容易引发不必要的讨论；
• 在工程实践中，函数应该尽量不修改入参，这是一个基本素养。

所以更推荐的做法是：排序可以原地做（面试中一般不纠结这个），合并结果放入新的merged数组。这样代码逻辑更清晰，也更容易向面试官解释。

4. 面试追问与变体：把一道题吃出一串题

4.1 变体一：插入区间

面试官非常喜欢在合并区间的基础上加一个追问：现在是“给定一个新的区间，把它插入到已经排好序且互不重叠的区间列表里，返回合并后的结果”。

有两种做法：

一种是直接线性扫描，把新区间当作普通区间走一遍合并逻辑，时间复杂度 O(n)，空间复杂度 O(n)。这种解法没问题，只是要注意新插入区间可能和左右多个区间合并，也可能插到列表末尾，还可能一个都不重叠，正好放到中间。

另一种是先用二分查找找到新插入区间应该放的位置，再做局部合并，代码复杂度高一些，但在某些场景下有性能优势。面试时第一种就足够了，重点是把“插入”这个动作降解为“合并”这个已解决问题，讲清楚逻辑就行。

4.2 变体二：区间交集

另一个常见的变体是“给定两个已经合并好的区间列表，求它们的交集”。这道题用的是双指针，每次取两个列表中当前指针所指区间的重叠部分，然后移动右端点较靠前的那一侧指针。思路和合并区间有关联但又不完全一样，面试时能主动提出这道题会显得你脑子里的知识是成体系的，而不是一题一题死记的。

4.3 变体三：最多能保留多少不相交区间

还有一道经典的区间调度问题：给定一些区间，选出尽量多的互不重叠的区间。做法是按右端点排序，然后贪心选择。它和合并区间看似相反（一个是合并重叠，一个是避开重叠），但底层都对“排序后扫描”这一范式有很强的依赖。如果面试官让你从合并区间引申到调度问题，你能迅速切到按右端点排序的贪心思路，会是很加分的表现。

4.4 高频易错点速查表

为了让读者排查方便，我把这个题族里最常见的错误整理成一张表：

这张表现在放在这里，等你哪次调试不过时再翻回来，一眼就能定位问题。

5. 聊点代码之外的东西

5.1 面试官想从这道题里听你说什么

我后来做过几次模拟面试的面试官，发现代码写对只是门槛，真正拉开差距的是候选人能不能讲清楚三个点：

• 为什么排序？因为要消除“回溯”这个复杂度来源，让问题线性化。
• 为什么只用维护最后一个合并区间？因为排序之后前面的区间已经处理完毕，后续区间只可能与最后一个产生重叠。
• 为什么合并时取max？因为右端点可能是新的更大，也可能是旧的更大，两者都要考虑。

这三个点其实在本文前面都出现过。能主动讲出它们的候选人，通常对这道题有真正的理解，而不是背了一个模板。

5.2 复杂度分析要脱口而出

时间复杂度：排序是 O(n log n)，扫描是 O(n)，整体 O(n log n)。

空间复杂度：如果只算额外空间（不包含排序和结果），是 O(1)；但在实际面试中，结果数组merged最多存放 n 个区间，所以更严谨的说法是 O(n)。排序本身在 Python 的 Timsort 实现中也会占用额外的辅助空间，这个视语言而定，面试时提到排序的空间消耗即可。

说复杂度的时候别只报一个结论，要带一句解释，这样面试官才会觉得你是真的算过。

5.3 从“刷题日记”到“知识体系”

我自己的经验是，刷题最忌讳一道一道孤立地刷。合并区间这道题，天然连接到排序、贪心、双指针、区间调度、扫描线等多个高频考点。你完全可以用它做枢纽，把相关的知识串起来：

• 由“排序后扫描”想到区间调度、会议室问题；
• 由“双指针求交集”想到合并两个有序数组、链表融合；
• 由“插入区间”想到有序结构中的插入与合并；
• 由“扫描线”想到天际线问题、矩形面积问题。

这种串联式刷法，一道题能顶十道题的效果。我在准备面试的时候，每次刷完一道题都会花十分钟想一想：这道题跟我之前哪几道题有关？能不能改一个条件变成另一道题？这个习惯帮我省了很多时间。

个人经验收尾

最后说点我自己的体会。合并区间这道题我前前后后手写了很多遍，几乎每次写出来的版本都不一样——最早是各种if分支嵌套，后来学会了max简化，再后来才意识到简化背后是对“闭区间重叠定义”的深刻理解。它让我真正明白了一个道理：很多算法题不是不会写，而是没有把“为什么可以这样写”想清楚。如果你现在还在反复调试边界，真不用急，这道题多“错”几次反而比背答案更有价值。下次再遇到“合并区间”，尝试在纸上先画出三种重叠关系，再动手，你会发现自己比上一轮稳得多。