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(keylambda 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(keylambda x: x[0])使用左端点排序。如果你忽略 key直接用intervals.sort()在 Python 里也能工作因为列表会按字典序比较子元素第一个元素相同时才会比较第二个元素。但为了语义清晰、避免依赖 Python 默认规则我更喜欢显式指定keylambda 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,3],[2,6],[8,10],[15,18]]普通重叠[[1,6],[8,10],[15,18]][[1,4],[4,5]]端点相接也算重叠[[1,5]][[1,4],[2,3]]完全包含不能被反方向缩短[[1,4]][[2,3],[5,6],[4,7]]乱序输入排序后能正确合并成两段[[2,3],[4,7]][[1,4],[0,0]]乱序且不重叠[[0,0],[1,4]]把这些用例跑通后基本可以覆盖这道题绝大部分易错分支。尤其是[[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, keylambda 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 按需优化与个人体会我在实际刷题中有一个明显体会不要一上来就在合并区间上用二分、差分这些技巧来显示自己会得很多。两步