企业官网建设流程全解析

1. 第14题真正让人卡住的不是算法，而是三个小决策

我第一次做力扣hot100第14题合并区间时，正在准备一场算法轮面试。读到题目时第一反应是：这不就是把重叠在一起的线段并起来吗，感觉不难。真把编辑器打开，我发现自己对三个问题并没有立刻给出坚定答案：重叠的判断条件到底用什么比较？已经合并过的区间，右边界要保留还是直接更新成新来的区间右边界？直接在 Python 里把interval追加进结果列表，会不会留下什么隐患？

如果你也被其中任何一个问题绊住过，别担心，这几乎是所有刷到这题的人都会经历的过程。合并区间是区间类题目的地基，也是典型的“题目一句话、细节十行代码”的代表。它的意义不在于考你某个冷门数据结构，而是检验三样基础功：排序意识、边界条件处理、用贪心思路把“区间重叠”抽象成可比较的数学关系。

从题目本身说起，输入是一个二维整数数组，每一项代表一个闭区间[start, end]，任务是把所有有重叠部分的区间合并成一个区间。比如[[1,3],[2,6],[8,10],[15,18]]会变成[[1,6],[8,10],[15,18]]。再看经典用例[[1,4],[4,5]]，输出是[[1,5]]，也就是说两个区间端点相接时也算重叠，需要合并，这个细节后面会重点展开。

这道题即使不学任何高级算法，也能靠两层循环硬做出来：先拿第一个区间去和后面所有区间比较，有重叠就融合，然后重复这个过程。但这么做有两个问题，一是修改原区间后要反复回看，写起来很容易在索引上迷路；二是时间复杂度容易退化成 O(n^2) 甚至更高，在大数据量下很难看。所以题目真正的价值，是带你建立一套“先排序，再单次扫描”的通用思维，这套思维在今天之后会遇到的大量区间题里都通用。

1.1 合并区间的直觉：用一张线段图理解“并集”

把每个区间想象成一条画在数轴上的线段，两个线段只要有重合，就把它们整体看成一个更大的线段。你可以随手画几组区间：

区间A: [1, 4] 区间B: [3, 7] 合并后: [1, 7]

也可以画包含的情况：

区间A: [1, 10] 区间B: [3, 5] 合并后: [1, 10]

无论哪种重叠，数学上都在求并集。一个区间的左边界取两者较小的左边界，右边界取两者较大的右边界。难点是：如果同时给了几十个区间，它们可能交叉、包含、首尾相接，随便挑两个肉眼去并很容易漏掉“A 和 B 合并后，B 又和 C 重叠”这种连锁反应。

所以必须找到一种方法，让这些区间按照某种顺序变得规律，再一条一条处理。

1.2 为什么很多人无法一次写对，关键在决策点

如果你把官方答案背下来，会发现代码不到二十行。但正是这十几行代码，藏着几个非常容易出错的决策点：

• 重叠条件的等号要不要加对位置；
• 新的右端点能不能直接覆盖旧的右端点；
• 排序之后，原列表会不会被意外修改；
• 返回的结果中，元素到底应该拷贝还是引用原来列表里的子列表。

这些问题不通过实战踩一遍，很难靠背诵形成肌肉记忆。这篇文章会把每条决策点都拆开讲透，你读完再看这题，会发现它不是“背答案题”，而是一道非常典型的“模型题”。能用好合并区间的模型，你后面做插入区间、区间交集、无重叠区间都会轻松不少。

2. 为什么“先排序”不是套路：贪心合并成立的底层逻辑

很多人第一次看题解时会有一个疑惑：合并区间为什么要排序？如果不排序，我照样可以用一个结果列表去比，为什么要多此一举？

你得先意识到，无序情况下做合并，本质上是在做“任意两两关系判断”。区间在数轴上没有确定顺序，你永远不知道当前区间会不会和之前已经处理完的某一个老区间再次重叠，因此最简单的想法必须反复回溯，比较次数自然就上去了。一旦按左边界从小到大排序，整个问题就从一个“图关系”变成了“线性推进”，因为你可以确信：新区间的左边界一定不会小于已经处理过所有区间的左边界，所以它只可能往右延伸，不可能和过去的线段产生新的交叉，除非它碰到了当前结果中最靠右的那根线。

2.1 无序状态下你被迫做两两比较，排序后你只需要看“最右侧尖兵”

想象你在数轴上一根一根地放置区间。无序放置时，每次放进来一根新线段，都要回头检查它是不是和之前任意一根已放好的线段重叠。这样每根都要和历史数据比较，成本是 O(n^2)。

但如果先把所有线段按左端点排好，它们就像排队一样，新来的线段的起始点永远在旧线段的右侧。这时候你根本不需要关心“老区间里是否有一根偏左的线段能与新线段相连”，因为老区间之间已经被合并成若干互不重叠的大段。新区间的左端点比这些大段的左端点都大，它只会和最后那个大段产生交集。所以你只需要维护一个变量：当前所有已合并区间的最右端点，或者更准确地说是结果列表中最后一个区间的右端点。

这个“最右侧尖兵”决定了当前合并的进度。新来的区间左边界只要不超过这个尖兵，就一定能被当前的合并结果吸收；一旦它超过了这个尖兵，说明当前这一段彻底结束了，需要开启新的一段。

2.2 三种重叠形态和一个判断条件

其实面试里画几个图，把区间重叠关系归纳一下，会得到三种形态。

第一种：普通相交。新区间起点落在老区间内部，终点向外延伸。比如[1,4]遇到[3,6]，合并结果是[1,6]。

第二种：完全包含。新区间整体落在老区间内部，比如[1,10]遇到[3,5]。此时新区间的终点不大于老区间的终点，合并结果应该保持不变，仍为[1,10]。

第三种：不相交。老区间完全结束之后，新区间才到来。比如[1,2]遇到[3,4]，二者没有重叠。

还有一个特殊情况是端点相接，比如[1,4]和[4,5]。在区间题中通常认为它们也算重叠，因为它们并集连续覆盖了[1,5]，这是力扣合并区间题目的默认规则。

这三种形态乍看要分情况讨论，但实际上都能归一成一个判断。先排序，再定义一个当前合并区间为merged[-1]。遍历到新区间[start, end]时，核心问题只有一个：

start 是否小于等于 merged[-1][1]？

如果start > merged[-1][1]，说明新区间起点已经把已合并区间的右边界甩在身后，肯定不相交，开启新区间；否则不管新区间是完全包含还是部分相交，都需要合并。合并时，右边界用max(merged[-1][1], end)更新，这样完全包含的形态也不会出错。

你可以试着把三种形态带入这个条件，会发现它们的差异全部被吸收了。这也是这题的精妙处：不需要一大堆 if 分支，有序加上一个比较条件，就能让所有情况收敛。

2.3 严谨性：为什么只需比较结果集的最后一个区间

有人会追问：如果前面合并出的若干区间彼此并不相连，而新区间起点很远，我们判断它只和结果集最后一个区间比较，会不会漏掉它其实能贯穿到某个更靠前的区间？答案是不会。

因为所有新区间的起点都按升序排列。在扫描过程中，结果集merged里的区间已经保证互不重叠，并且从左到右排列。新区间的起点一定大于等于所有已处理区间的起点。如果它的起点已经大于merged[-1]的右边界，那么它必然也大于merged[-1]之前所有区间的右边界，因为那些区间的右边界只会更靠左。一个起点都超过终点更靠右的线段，自然不可能和更靠前的区间重叠。

这个论证也是合并区间算法正确性的核心。它依赖的正是“排序”这个预处理，所以你再理解题解的时候，千万不要把排序当成可有可无的步骤，它是整个贪心策略成立的前提。

3. 可直接复现的 Python 实现，从“能跑”到“放心提交”

接下来给出我平时刷题和面试时最常用的一版实现。它不算最短，但每一步都写得清晰，适合你理解逻辑，也适合放进简历项目里做注释。

from typing import List def merge(intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] # 原地按左端点排序 intervals.sort(key=lambda x: x[0]) merged = [] for start, end in intervals: # 结果为空，或者新区间的起点超过了当前合并段的最右端 if not merged or start > merged[-1][1]: merged.append([start, end]) else: # 有重叠，更新最右端 merged[-1][1] = max(merged[-1][1], end) return merged

这段代码放到力扣的执行环境里可以直接运行。下面把每一行拆开讲，重点不是解释语法，而是解释为什么这样写是对的。

3.1 标准版实现与逐行解读

首先是空判断。if not intervals处理的是传入空列表的情况。其实不加这行，后面循环自然跳过，直接返回[]，结果也不会错。但面试时加一行能传递一个信号：你考虑过边界条件。

其次是排序。intervals.sort(key=lambda x: x[0])使用左端点排序。如果你忽略 key，直接用intervals.sort()，在 Python 里也能工作，因为列表会按字典序比较子元素，第一个元素相同时才会比较第二个元素。但为了语义清晰、避免依赖 Python 默认规则，我更喜欢显式指定key=lambda x: x[0]。

然后是主循环。for start, end in intervals自动把每个子区间拆成起点和终点，代码阅读性更好。循环内部第一个if是开启新区间的条件，第二个else是合并条件。merged[-1]永远是当前正在合并的最后一个区间，用它存储当前段的最右端点。

合并时用max(merged[-1][1], end)而不是merged[-1][1] = end，这是许多初学者极其容易犯错的地方。从数学上讲，合并后的右边界应该取两个区间右端点中较大的那个，新区间虽然起点更大，但终点可能更小，比如[1, 8]遇到[3, 5]，直接赋值为 5 会把已经覆盖到 8 的边界缩回去，产生严重错误。

3.2 安全返回的细节：切片赋值、入参与可变引用

上面这个版本里，merged.append([start, end])创建了一个全新的列表，不会和原intervals中的子列表共用引用。这是比较安全的写法。

不过网上的许多版本写的是：

merged.append(interval)

区别在哪里？在于你到底想不想在返回结果里保留“指向原始数组子列表的引用”。如果你只是刷题，两者在大多数场景下结果一样，因为力扣判题只看返回结果，并不会检查你原数组有没有被顺手改掉。但在实际工程中，直接把interval追加进去，后续一旦执行merged[-1][1] = ...，会同步修改原数组里对应的那个子列表，造成非常隐蔽的副作用。

如果你希望完全避免这种引用的纠缠，标准做法是追加一个切片副本：

merged.append(interval[:])

或者像我上面的写法一样，把start和end解构出来，再merged.append([start, end])。这样既复制了值，也让后续对merged的修改不会污染原始数据。

3.3 用来验证正确性的边界用例清单

刷题不能只看示例就提交，要对极端情况做验证。我在本地跑代码时，通常会准备下面这组用例：

把这些用例跑通后，基本可以覆盖这道题绝大部分易错分支。尤其是[[1,4],[4,5]]和[[1,4],[2,3]]这两组，前者验证等号，后者验证max是否被正确使用。

4. 我自己写这套逻辑时反复踩的三个坑

有些坑是键盘敲到一半才突然意识到的，有些则是提交之后被测试用例狠狠教育过。既然这篇文章的定位是“能直接抄作业”，我就把个人踩坑记录整理出来，按出错频率从高到低排序。

4.1 判断条件少了一个等号，或把“相切”误判为“不相交”

合并区间题目里，[1,4]和[4,5]是要合并的，因为它们端点相接，并集覆盖了[1,5]。如果你把不重叠条件写成：

if not merged or start < merged[-1][1]:

你就会认为“只有终点严格大于新区间起点时才是相交”，从而把start == merged[-1][1]的情况丢进新区间，最终得到错误输出[[1,4],[4,5]]。

正确的不重叠条件应该是start > merged[-1][1]，也就是只有新区间起点严格超过当前合并区间的最右端，才说明二者真正脱节。一旦二者相等或者新区间起点更小，都应该并入同一个合并段。这个等号的位置决定了一类区间题的正确性，建议你自己写一个[[1,4],[4,5]]用例跑一遍，加深印象。

4.2 该用 max 的地方直接用了 interval[1]，丢掉了已经覆盖得更远的尾巴

继续看这个例子：

intervals = [[1, 10], [2, 3]]

按左端点排序后，先记录[1,10]，处理[2,3]时发现它被完全包含。如果合并代码写成：

merged[-1][1] = end

合并后的右边界会变成 3，结果返回[[1,3]]，而正确答案显然是[[1,10]]。10 这个边界才是它们共同覆盖的最远点，新区间的终点 3 不能代表并集。

这告诉我们，合并时右边界必须用max，除非你能保证新区间的终点一定比旧区间的终点大。但排序只能保证新区间起点更大，无法保证终点也更大，所以max是必须的那一步，而不是可选的防御式写法。

4.3 sort、sorted 与原地排序的副作用，以及 res.append(interval) 的引用别名问题

Python 的list.sort()是原地排序，会直接改变传入的intervals列表顺序。如果你写的函数被别处使用，或者调用者不希望原始区间顺序被改动，这就可能成为隐性问题。使用内置函数sorted(intervals, key=lambda x: x[0])则不会修改原列表，而是返回一个新排列副本。

还有一个更隐蔽的坑：

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

这段代码的问题在于merged.append(interval)添加的是原列表子列表的引用，不是拷贝。当后续发生合并，执行merged[-1][1] = ...时，会连带修改intervals中的对应子列表。虽然力扣的判题系统不关心这种情况，但如果你把这段逻辑抽象成工具函数并供业务调用，就很容易出现“调用完函数，原数据也变了”的诡异现象。

我个人的习惯是：凡是返回结果中包含从输入结构中拆分出来的多个值，尽量在返回前创建新的子列表，不直接沿用原引用，避免给别人留坑。如果真的在乎性能，也至少要弄清楚潜在副作用，再考虑是否保留这种写法。

5. 合并区间只是入口：面试官常在同一棵树上挂满变体

很多人刷完这题就急着赶下一道，觉得“已经会了”。但合并区间最大的价值，是帮你建立区间题的思维范式。在算法面试中，面试官看到你会做合并区间，下一步往往会直接追加变体。如果只背了当前答案，不一定能接住。

5.1 五个高频变体各自改了哪个条件

第一个变体是插入区间。题目会给你一列已经按起点排好序且互不重叠的区间，再给一个新区间，要求插入并合并。思路无非是线性扫描：在新区间左侧的部分原样输出；与新区间有重叠的部分持续吸收；新区间右侧的部分再原样输出。相比合并区间，它天然有序，少了一次排序。

第二个变体是区间交集。给定两个已经按左端点排序的区间列表，要求返回它们的交集。这题使用双指针，每次判断两个区间的重叠条件，以及哪个区间先结束就先移动哪个指针。交集条件是max(left1, left2) <= min(right1, right2)。

第三个变体是无重叠区间。给定若干区间，问最少移除多少个区间可以让剩余区间互不重叠。解法是排序后按右端点贪心：能保留就保留，不能保留就优先移除右端点更大的那个。核心思想从“取并集”换成了“保留最不占空间的那个”。

第四个变体是用最少的箭引爆气球。区间代表气球直径，你可以在某个坐标射箭，希望一箭穿过尽可能多的区间。它和无重叠区间几乎同源，只要区间有重叠就能用同一支箭，策略仍然是按右端点贪心。

第五个变体是区间并的总长度。先做一次合并区间，最后统计每个合并区间的长度之和。

你会发现这些变体的核心步骤几乎都有“排序”和“判断两个区间是否重叠”。差别只在于两个区间重叠后，你如何处理边界：是取并集，取交集，还是淘汰其中一个。

5.2 对模型的理解，才是面试加分项

如果面试时问我合并区间这道题，我一般会多说一句：这道题和“区间覆盖问题”紧密相关，排序后只维护当前最右端点就能做到线性扫描，本质是贪心。再延伸一句：如果输入本身就是有序的，那连排序都能省掉，整个合并过程就是一次 O(n) 的扫描。

这句话可能不会直接影响算法正确性，但能让面试官感受到你不只是在背代码，而是建立了区间题的完整知识框架。框架的价值在于：面试官无论往哪个方向追问，你都能从他的问题中找到“其实这题改的是哪一部分”的答案，而不是每次都是重新学一道题。

6. 再聊几句复杂度与“输入已有序”的进阶玩法

合并区间这道题通常被划分为中等难度，原因是排序之后还需要一次巧妙的扫描。看似简单，复杂度往往是你向面试官展示基本功的关键入口。

6.1 复杂度的真实构成

先说时间。排序阶段的时间复杂度是 O(n log n)，扫描阶段是 O(n)，总体是 O(n log n)。其中 n 是区间个数。排序是整个算法的大头，扫描阶段不会成为瓶颈。

空间上，大多数实现需要一个结果列表merged，最坏情况所有区间都不重叠，结果列表也会存下 n 个子区间，因此额外空间是 O(n)。如果再把 Python 排序内部使用的临时空间也计入，Timsort 最坏情况可能需要 O(n) 级别的额外空间。但刷题讨论时，通常认为原地排序本身不算那份太大的额外开销，而merged作为返回值是否计入额外空间则取决于题目约定。面试时你说清楚“结果列表本身算输出，不算额外空间；如果实现中每次都创建新区间，实际上也占用 O(n)”就够了。

6.2 如果面试官追加“输入本身有序”，你能答出什么

有一种情况：面试官不是直接让你解力扣原题，而是给了一个更贴近业务的条件，“我手上的区间已经按起点排好了，还能优化吗”。

如果输入已经有序，那合并部分只需要做一次从左到右的扫描，时间复杂度会直接降到 O(n)。前提是初始就保证每个区间按起点升序排列，并且不会出现“先出现一段极大区间、后面又冒出一个起始点更小”的乱序问题。

另外，在已经有序的前提下，如果问题是“查询某个点落在多少个区间里”，你还可以考虑用二分查找加速。比如预先收集所有区间起点，然后用bisect找到第一个起点大于目标点的位置，就能快速判断目标点处于哪个区间范围内。这已经不完全是合并区间本身了，但它展示了你对“有序数据可以用二分”的敏感度。

如果题目变成“频繁向一组有序区间中插入新区间，同时要求保持有序”，你的答案还能更进阶：先二分找到第一个与新区间重叠的区间，再把左右受影响的区间合并起来。由于列表的插入本身需要移动后续元素，整体仍可能是 O(n)，但你至少让面试官看到你清楚二分能优化“在哪里开始合并”这一步。

6.3 按需优化与个人体会

我在实际刷题中有一个明显体会：不要一上来就在合并区间上用二分、差分这些技巧来显示自己会得很多。两步