刷LeetCode刷到区间题的时候很多人第一反应是这有什么难的结果一写就错一改就乱。标题写的是Leetcode 130 合并区间 | 插入区间我猜这里大概率是笔误实际想说的应该是LeetCode 56合并区间和57插入区间这两道题。这两题在LeetCode热门100题里长期霸榜周赛里也隔三差五换个包装出现比如合并重叠区间会议室扎气球这些变体核心模型全是同一个。这篇就把合并区间和插入区间从头到尾拆开揉碎讲清楚排序为什么这样排、指针为什么这样走、边界条件到底有多少个坑以及真正面试/工程里怎么用这套思想。1. 区间题为什么值得花时间死磕从LC周赛到工程实践先说结论区间题的考察密度非常高而且它考的从来不是你会不会写循环而是你脑子里有没有把问题抽象成区间模型的习惯。LeetCode热题100里区间相关题目占了至少五六道周赛430那一期的变体题我当时做过记录本质上也在考区间合并和冲突判断。换句话说这两道题不是刷完就扔的孤岛它们是整个区间问题族的入口。工程里的真实场景也特别多。比如后台系统要合并用户在线时长一个用户今天登录了三次每次登录时段有重叠你要算出他实际在线多少小时比如会议室的预订系统要判断一个新会议能否插入到已有日程里再比如网络运维要把一堆有交叠的IP段合并成一个大的网段。这些需求提取一下全变成了一句话给定一堆区间合并它们或者往有序区间列表里插入一个新的且保持无重叠。所以我一直觉得区间题是那种刷一道顶十道的题型。它的核心不是某个巧妙的算法而是一套非常固定的思考流程要不要排序、按什么排序、怎么处理相邻关系、边界条件怎么收尾。把这套流程练成肌肉记忆后面遇到的变体题都能套。2. 合并区间LeetCode 56排序贪心一个指针搞定的事2.1 核心思路为什么必须先按左端点排序合并区间的经典解法是排序贪心。但很多人会问为什么非要排序不排序不行吗不排序你每拿到一个新区间都要和当前合并结果里的每一个区间比较并尝试合并复杂度是O(n²)而且合并完以后可能还要反复回溯——因为你无法确定后面还有没有区间能和刚合并出来的新区间再次重叠。排序的意义在于按左端点排序后贪心策略有了一个确定的推进方向后面的区间只可能从右边延伸出来不会跑到当前合并区间的前面去。打个比方你有一堆有重叠的长条积木想用尽量少的盒子把它们装起来。如果不排序你得来回试错如果按每根积木的左端点位置从前往后排好那么当你把当前盒子扩展到能盖住的最远右端点时就可以放心地看下一根积木因为它不可能再往左伸出更长的部分。2.2 代码走读从排序到合并的完整实现def merge(intervals): if not intervals: return [] # 按左端点排序这是整个题的前提 intervals.sort(keylambda x: x[0]) res [intervals[0]] # 先取第一个区间作为当前合并目标 for l, r in intervals[1:]: # res[-1][1] 是当前合并区间的最右端点 if l res[-1][1]: # 有重叠更新右端点取较大值 res[-1][1] max(res[-1][1], r) else: # 无重叠直接开新区间 res.append([l, r]) return res这段代码很短短到很多人背下来了但背代码没用要理解两个关键点。第一合并条件为什么是l res[-1][1]而不是。因为区间相交包括刚好端点相接的情形。比如[1, 3]和[3, 5]它们有一个公共端点3实际业务中这两个区间是连续的可以合并成[1, 5]。如果你写了这个合并就被漏掉结果注定错误。这个细节在LeetCode上属于边界测试点在线面试的白板书写里更是高频翻车点。第二合并时右端点为什么用max而不是直接赋r。因为当前区间可能已经覆盖了很远的范围比如res[-1]是[1, 10]现在来了个[2, 3]它完全在[1, 10]里面。如果直接res[-1][1] r右端点会从10被改小到3后续区间的合并判断就全错了。这属于看着代码没问题一跑用例就炸的典型低级错误原因就是没有想清楚合并操作的本质是取两个区间右端点的较大值而不是用新区间覆盖旧区间。2.3 排序细节默认排序不一定对key必须写清楚Python里intervals.sort()也能跑通因为默认按列表的字典序排序先比左端点再比右端点。但这里有个隐患如果intervals是别的数据结构比如自定义类实例或者你后面要用其他语言Java的二维数组默认排序行为就不一样不显式指定keylambda x: x[0]你就是在赌默认排序规则恰好符合需求。更关键的是按左端点排序后只需要比较相邻区间这个结论是贪心策略成立的基础。面试时把这句话说出来比闷头写排序更有说服力因为任意两个区间若相交必然存在一条相邻相交的传播链从左至右合并即可覆盖所有情况。2.4 复杂度与空间优化时间复杂度O(n log n)瓶颈在排序空间复杂度如果不算输出结果就是O(log n)排序栈算上结果则是O(n)。工程里如果区间数量很大可以考虑原地修改intervals来省内存但不建议面试这么干因为可读性差。我在LC周赛430的签到题里就见过类似场景给一堆形如[start, end]的区间要求返回合并后的数量。当时不少人用了双重循环暴力比较数据量一大直接超时。其实把合并逻辑写出来最后返回len(res)就是答案。所以这个骨架代码值得放在笔记里反复看它是很多变体题的地基。3. 插入区间LeetCode 57在有序列表里放一个新区间3.1 这题和合并区间的关系插入本身就是合并的一种特殊形式插入区间的题面是有一个已经按左端点排序且无重叠的区间列表给你一个新的区间把它插进去如果发生重叠就合并最后返回新的无重叠列表。很多人第一反应是先把新区间append到列表里然后调用一遍合并区间代码。这确实能通过时间复杂度和合并区间一样是O(n log n)。但仔细看题面输入的区间列表已经有序且不重叠了你做的事情相当于往有序数组里插一个元素排序是多余的。更优的做法是一趟线性扫描因为原来列表已经有序新区间只会扰动局部区域它左边的部分完全不受影响右边可能有若干区间要被合并再右边又是完全不受影响。能把问题拆成三段就说明这道题的本质是定位而非排序。3.2 线性扫描的完整实现三段式处理def insert(intervals, newInterval): res [] i 0 n len(intervals) # 第一阶段把完全在新区间左边的区间直接收下 while i n and intervals[i][1] newInterval[0]: res.append(intervals[i]) i 1 # 第二阶段合并所有与新区间相交的区间 while i n and intervals[i][0] newInterval[1]: newInterval[0] min(newInterval[0], intervals[i][0]) newInterval[1] max(newInterval[1], intervals[i][1]) i 1 res.append(newInterval) # 第三阶段把右边剩下的区间直接收下 while i n: res.append(intervals[i]) i 1 return res这里的三个while各司其职非常清晰。第一个while判定条件是intervals[i][1] newInterval[0]意思是当前区间整个都在新区间的左边没有任何交集第二个while判定条件是intervals[i][0] newInterval[1]意思是还有区间和不断被扩展的新区间相交就一直合进去第三个while就是把剩下的收尾。有个容易漏的细节第二阶段里newInterval是被原地更新的。每合并一个区间它的左端点可能变小右端点可能变大于是下一个区间是否相交的判断也要基于新边界而不是原始newInterval的边界。我见过太多人在这里写了个单独的cur_left, cur_right变量用来存当前合并区间其实直接复用newInterval是更简洁的写法因为反正最后它就是要被放进结果里的。3.3 二分查找优化从O(n)到O(log n n)既然输入列表有序且无重叠理论上是可以用二分先定位新区间左边最后一个完全不相交的区间的位置这样前两个阶段可以更快。找位置用bisect或者手写二分代码如下import bisect def insert_binary(intervals, newInterval): n len(intervals) # 找到第一个右端点 newInterval[0] 的位置 left bisect.bisect_left([r for _, r in intervals], newInterval[0]) # 从left开始逐个合并直到左端点 newInterval[1] i left while i n and intervals[i][0] newInterval[1]: newInterval[0] min(newInterval[0], intervals[i][0]) newInterval[1] max(newInterval[1], intervals[i][1]) i 1 return intervals[:left] [newInterval] intervals[i:]这里left bisect.bisect_left([r for _, r in intervals], newInterval[0])的意思是找到第一个右端点不小于新区间左端点的区间它和它后面的区间才可能发生重叠。这样前面的intervals[:left]直接切走不需要遍历。这个写法时间复杂度可以描述成O(log n m)m是需要合并的区间个数最坏情况下仍为O(n)但常数小了很多。面试时能主动提因为列表有序可以先用二分压缩需要线性扫描的长度是加分的点。3.4 边界场景区间完全被吞没的情况有一种情况必须单独测新区间完全被已有区间覆盖比如intervals [[1, 5]]newInterval [2, 3]。跑上面的代码第二阶段第一次合并后newInterval还是[2, 3]但i已经走到头了于是newInterval被append进去结果变成[[1,5], [2,3]]。这就不对了输出应该还是[[1,5]]因为[2,3]已经包含在[1,5]里。问题出在第二阶段的条件和第三阶段的衔接上。如果newInterval被某个区间完全包含其实这个新区间就应该归并到已有区间里而不是作为独立元素append。我重新调整一下写法更稳妥def insert(intervals, newInterval): res [] i 0 n len(intervals) while i n and intervals[i][1] newInterval[0]: res.append(intervals[i]) i 1 if i n: # 新区间在最右边 res.append(newInterval) return res # 直接修改intervals[i]让重叠区间的合并结果落在它上面 while i n and intervals[i][0] newInterval[1]: newInterval[0] min(newInterval[0], intervals[i][0]) newInterval[1] max(newInterval[1], intervals[i][1]) i 1 res.append(newInterval) while i n: res.append(intervals[i]) i 1 return res其实上面的原始写法在[1,5]插入[2,3]时会输出[[1,5],[2,3]]吗我们跑一遍第一阶段intervals[0][1] 5 newInterval[0] 2不成立跳过第二阶段intervals[0][0] 1 newInterval[1] 3成立合并后newInterval [1,5]i变为1第三阶段没有剩余区间append newInterval得到[[1,5]]。所以原始写法在这个case下反而正确因为合并后的newInterval被更新成了覆盖范围更大的区间。真正需要警惕的是另一种情况newInterval落在两个已有区间之间但和两者都不重叠比如intervals [[1,2],[5,6]]newInterval [3,4]。跑代码第一阶段收下[1,2]第二阶段intervals[1][0] 5 newInterval[1] 4不成立循环退出append newInterval第三阶段收[5,6]。结果[[1,2],[3,4],[5,6]]正确。所以代码的核心逻辑没有大坑但如果你像我一样习惯用跳过左右两边处理中间的模板一定把覆盖更新的细节想清楚线上笔试没有调试机会边界用例自己先在草稿纸上过一遍。4. 从合并到插入的通用套路区间问题的内核是相交判定4.1 把区间相交的四种情形一次搞清楚我在面试模拟中问过很多人两个区间[a, b]和[c, d]什么时候不相交回答通常不完整。其实不相交只有两种情况b c第一个在第二个左边或者d a第一个在第二个右边。因此相交的条件就是两个不相交条件的补集a d且c b这也等价于max(a, c) min(b, d)意思是两个区间的左端点的较大值不超过右端点的较小值。这个交叉条件在合并区间、插入区间、会议室问题里全都适用。我建议你把这个条件记住遇到区间题第一件事就是套它。4.2 区间题的通用解题步骤从这两道题可以提炼出一个解题模板先看清楚输入区间是否有序、是否重叠。插入区间给你有序无重叠那排序这步可以省。如果无序先按左端点排序。用一个变量或输出数组的最后一个元素维护当前合并区间的左右端点。逐个处理区间相交则合并不相交则开新区间。最后统一处理收尾——合并区间题的循环结束后别忘了把最后一个合并区间加入结果上面的代码用先放第一个进res再依次合并的方式规避了这个问题。前端时间我在LeetCode热门100题里看到会议室系列的讨论很多题解的核心代码和上面几乎一模一样。比如会议室II要求判断最少需要多少个会议室本质就是区间重叠的最大深度解法可以转换成排序后扫描端点遇到开始时间1遇到结束时间-1峰值就是答案。这和合并区间的排序贪心是同一套思考逻辑只是统计维度不同。4.3 引申变体一道题带出一片题评论区里常有人说合并区间和插入区间没什么用工作里又用不到其实是因为只看了题面没看透模型。把它们拆开看给你一堆区间返回合并后的区间列表 → 合并区间给你一堆有序无重叠的区间插入一个新区间返回新列表 → 插入区间给定一堆会议时间判断一个人能否参加所有会议 → 排序后检查相邻重叠给定一堆课程/会议时间问最少需要几个教室 → 端点扫描求最大重叠数在x轴上扎破所有气球每支箭可以扎破重叠的气球问最少几支箭 → 排序后贪心合并只是把重叠区间的公共右端点不断收紧每一道都是同一棵树上长出来的叶子。刷题最划算的方式从来不是追数量而是把一个模型的来龙去脉搞透。我自己的刷题指南里对区间题的要求就一句话合并区间能闭眼写出来插入区间能讲清楚为什么不需要排序。做到这两点上面的变体题基本都能推出来。5. 实测与避坑我在周赛和实际刷题中踩过的坑5.1 区间为空、长度为1、负数区间合并区间和插入区间都可能有空输入必须开头就把if not intervals这种情况处理掉这是基本功。但还有两个测试用例经常被忽略长度恰好为1合并区间直接返回这个区间插入区间要判断newInterval插在它左边、内部、右边三种情况。负数区间比如intervals [[-10, -5], [-6, 0]]这两个区间其实相交-6 -5合并结果是[-10, 0]。有些人在纸上画图只画正半轴写代码的时候能跑对但推导分析时就容易漏掉。5.2 排序稳定性与key函数的选择合并区间选interval[0]左端点排序这一点确定后如果左端点相同排序后的顺序对结果有影响吗比如[[1, 4], [1, 2]]无论[1,2]在前还是[1,4]在前合并结果都是[1,4]所以稳定性不影响最终答案。这算是一个让人安心的结论。但插入区间题目明确说列表未重叠且已排序有的语言版本可能没严格保证左端点排序的稳定性可幸逻辑上也不需要稳定。我在实际工程中反而遇到过更隐蔽的问题右端点排序的混淆。比如最少箭数扎破气球这道题正确解法是按右端点升序排序而不是左端点。如果你调用了合并区间的肌肉记忆按左端点排序就会得出错误答案。所以每次拿到区间题先问自己一句这道题的关键决策是选左端点还是右端点排序合并区间选左端点是为了贪心从左往右推进扎气球选右端点是为了让每一箭尽量靠右、覆盖更多气球。排序端点不固定这恰恰是区间题最考验理解深度的地方。5.3 模拟面试复盘三个必须先问的问题我陪练过几次模拟面试候选人拿到合并区间立刻低头写代码我看着就着急。面试官在评价时往往不只看代码还看审题动作。拿到区间题尤其是插入区间建议你张嘴就问三句话输入是否已经有序且无重叠决定要不要排序、以及能不能二分区间端点的开闭性如何[start, end]是闭区间还是半开区间LeetCode默认闭区间但业务里可能不同比如会议结束时间和下一场开始时间相同是否冲突允许原地修改输入还是需要返回新数组影响空间复杂度和是否破坏数据问完这三个问题你已经比80%的直接开写的人得分高了。因为它们都直接影响核心算法选择而不只是装模作样的确认需求。5.4 周赛430那一类的实战体会上次LC周赛遇到一个区间合并的变形题目要求把重叠区间合并后返回整个覆盖长度不是区间列表。本质上是在合并区间的同时累加长度代码只需要在开新区间时把当前区间长度加上就行。很多人栽在没搞清楚当前合并区间何时截止一直在循环里重复累加。其实套路一样按左端点排序维护curL和curR每次遇到不相交区间就把curR - curL加到答案里。这题我在本地一次跑过因为合并区间的模板已经刻在脑子里了。还有一次做插入区间的周赛题题面稍微绕了一点新区间可能和左右两边都重叠形成一个大区间。这时候如果你套用线性扫描的三段式第二阶段里更新newInterval时要连着左边刚收入的结果也检查一遍否则可能出现res最后一个区间和新区间仍重叠但没合并的情况。我的建议是遇到这类变体第一步先老老实实把新区间append到列表里重新排序合并一遍保证AC之后再考虑优化成线性扫描。面试中先给正确解再给优化解是比一口气写最优解更稳的策略。6. 最后再分享一个从实践中来的区间题复习法区间题是我刷题列表里回看率最高的一类因为变体太多一段时间不碰就会手生。我自己摸索出来一个复习办法很简单把合并区间、插入区间、会议室、扎气球这四道题放在同一个备忘录里每次复习只允许自己看解题思路一句话和易错点然后默写代码跑样例。四道题跑完不超过二十分钟但效果比单刷十道新题都好。顺带说一个答题习惯方面的细节写完代码一定要自己举一个区间完全包含的例子在草稿纸上走一遍循环。比如intervals [[1, 10], [2, 3]]合并区间跑完应该输出[[1, 10]]如果写的是res[-1][1] r这种非max更新在这里就会当场露馅。一个简单的小用例就能筛掉一大半常见的粗心错误。区间题目看起来简单实际要踩的坑一点都不少希望这篇能帮你把从排序到合并、从插入到变体的这条线串起来下次不管在周赛还是面试里遇到都能稳稳地接住。