力扣第56题“合并区间”在力扣题库里算是一道标准的热题100在ACwing的算法基础课里它被直接归进了排序模板题那一类。刷过ACwing课的人看到这个标签就懂——这道题考的不是什么高深技巧而是你能不能看穿“区间合并”的本质就是一次排序加一次线性扫描。今天这篇我把这道题的题型定位、推导过程、代码细节、边界坑位一次讲透无论是刚入门刷题的新手还是准备面试想快速过一遍高频题的老手都能从这里拿到可以直接上手的方案。先说结论合并区间这道题第一步排序第二步维护一个当前合并区间第三步遇到完全不相交的区间就把上一个结果落盘。整个过程没有递归、没有动态规划、没有复杂数据结构靠的是一句话——“排序之后重叠关系变成相邻关系”。这个认知一旦建立这道题就不再有思考成本剩下的是写代码的熟练度问题。1. 题型定位这道力扣题为什么是排序模板题的“课代表”1.1 题目在说什么先把合并区间翻译成人话题目输入是一组二维数组每个元素是[start, end]表示一个闭区间。要求把所有“有交集”的区间合并成一个区间返回合并后的完整区间列表。注意这里的交集包括端点相连的情况比如[1,4]和[4,5]因为端点4重合也要被合并成[1,5]。力扣给的官方示例是输入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]没有交集原样输出。在ACwing的模板题单里这一题叫作“区间合并”模板它的标准解法就是分三步排序、扫描、合并。说白了它考察的是你能不能把一个看似需要 O(n²) 两两比较的问题通过一次排序降维成 O(n) 的线性问题。所以这道题真正要练的能力有两个第一识别“区间类问题先排序”这个套路第二把“合并逻辑”写对尤其是边界处理。这两个能力在后面的区间问题题海里几乎都是通用的。1.2 排序的关键作用把 O(n²) 的两两判断变成一次线性扫描如果不排序我们要判断任意两个区间是否重叠最直接的做法就是两两比较所有区间对复杂度 O(n²)。比如有 10 万个区间两两比较就是 50 亿次这在面试和在线评测里肯定是不能接受的。排序的价值在于将所有区间按照左端点从小到大排好之后区间之间的关系出现了强有序性。具体来说我们维护一个“当前合并区间”它有一个右端点 R。处理下一个区间时如果下一个区间的左端点 l 小于等于 R说明这两个区间一定有交集可以扩展当前合并区间。如果 l 大于 R那么当前合并区间就可以确定下来了因为它后面不可能再有区间和它有交集了毕竟后面所有区间的左端点都会大于等于 l自然也就大于 R。这个论证是整道题的核心也是面试时要当场说清楚的“贪心正确性”。想通这一点剩下的代码就是体力活。我在实际写题的时候喜欢把这种“排序后重叠关系变成相邻关系”的思路画在纸上画完一遍代码基本就自然出来了。2. 思路拆解排序 贪心扫描的完整逻辑2.1 排序规则为什么按左端点升序就够了既然要线性扫描排序规则就很重要。按左端点升序这是最优选择原因有两点第一左端点升序之后我们扫描到的每一个新区间它的起点都不可能比之前小这样“当前区间”才能按顺序向后推进。第二排序不需要自定义复杂规则。C 里vectorvectorint默认按字典序排序先比较first再比较secondPython 里 list 的排序也是逐元素比较。也就是说直接调用默认排序就已经得到了“按左端点升序左端点相同的按右端点升序”的结果。对本题来说右端点序无所谓影响不了结果所以直接排即可。这里顺带解释一个新手经常会疑惑的问题为什么要按左端点排而不是按右端点排如果按右端点排序虽然也能做但扫描时左端点无序会带来很多麻烦一个左端点很小但右端点很大的区间可能贯穿后面一堆区间导致合并判断变得混乱。按左端点排序是最符合“从左往右推进”直觉的。记住一个口诀区间合并先按左端点排序这是模板照做就行。2.2 合并规则什么时候更新右端点什么时候落盘扫描时我们维护两个变量L和R表示当前正在合并的区间。初始时把第一个区间赋值给它们然后从第二个区间开始逐个处理。每次拿到新区间[l, r]判断逻辑其实只有两种如果l R说明新区间和当前合并区间有交集合并后的右端点应该是max(R, r)。如果l R说明新区间和当前合并区间毫不相干当前合并区间已经“封口”把它加入答案数组然后把L、R更新为这个新区间的值。关键点在于max(R, r)。很多人第一次写会直接写R r这在新区间比当前合并区间短的时候会出错。举个例子当前区间是[1,10]新区间是[2,3]显然合并结果应该是[1,10]。如果写R r就会把右端点错误地缩短成 3吞掉了后面3到10的范围。所以合并时取max是必须的这也是最容易出错的细节之一。循环结束后别忘了把最后一个L,R加入答案。因为最后一个合并区间没有下一个区间来触发“落盘”逻辑需要手动补一次。2.3 用手推一遍标准样例用官方样例走一遍全过程逻辑会非常清晰排序前[[1,3],[2,6],[8,10],[15,18]]排序后其实这里已经有序[[1,3],[2,6],[8,10],[15,18]]初始化L1, R3。处理[2,6]2 3重叠合并R max(3,6) 6。当前L1, R6。处理[8,10]8 6不重叠把[1,6]加入答案更新L8, R10。处理[15,18]15 10不重叠把[8,10]加入答案更新L15, R18。循环结束手动把[15,18]加入答案。输出[[1,6],[8,10],[15,18]]和官方答案完全一致。3. 代码落地C 与 Python 的双版本实现3.1 C 版本默认 sort 够用但要知道它为什么够用C 解法最简洁的写法是这样的class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint ans; int L intervals[0][0]; int R intervals[0][1]; for (int i 1; i intervals.size(); i) { int l intervals[i][0]; int r intervals[i][1]; if (l R) { R max(R, r); } else { ans.push_back({L, R}); L l; R r; } } ans.push_back({L, R}); return ans; } };这里的sort(intervals.begin(), intervals.end())用的是默认排序规则对vectorvectorint来说就是按第一维升序第一维相同再按第二维升序。正好符合我们的需求。如果想要显式写可以加 lambdasort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[0] b[0] ? a[1] b[1] : a[0] b[0]; });两种写法都行面试时用默认 sort 加一句注释“默认按第一维排序即可”完全够用。3.2 Python 版本三行 if 清空思路附带别名坑提醒Python 版本可以写得更短也更贴近直觉class Solution: def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort(keylambda x: x[0]) ans [] for interval in intervals: if not ans or ans[-1][1] interval[0]: ans.append(interval) else: ans[-1][1] max(ans[-1][1], interval[1]) return ans这里的核心是利用ans[-1]充当“当前合并区间”。如果答案数组为空或者当前区间和最后一个结果区间没有交集就新开一段否则更新最后一个结果区间的右端点。有一个小坑要提醒ans.append(interval)会把interval这个列表对象的引用放进去而不是拷贝。如果后续有代码修改原intervals里的元素可能意外影响到已经放进答案里的内容。在本体算法里不会出问题因为后续只更新ans[-1][1]但如果你后面又对原数组做排序之类的操作就要小心别名副作用。稳妥一点可以直接ans.append([interval[0], interval[1]])拷贝一个新的列表。如果你不想用keylambda x: x[0]直接写intervals.sort()也行因为 Python 对列表的默认比较也是逐元素比较效果一样。但显式指定 key 可读性更好面试时也更容易表达意图。3.3 复杂度分析排序主导扫描线性时间复杂度上排序是 O(n log n)排序之后一遍线性扫描是 O(n)整体 O(n log n)。空间复杂度上如果不算输出数组C 的sort使用的是内省排序递归栈深度 O(log n)Python 的 TimSort 最坏情况也需要一些额外空间通常视为 O(n)。但刷题时这个空间基本不是瓶颈真正要记住的复杂度结论是排序 O(n log n) 扫描 O(n)。如果面试官问能不能省空间可以用原地覆盖的思路把排序后的数组本身当作输出空间用一个write指针覆盖前面已经处理完的区间class Solution { public: vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); int write 0; for (int i 0; i intervals.size(); i) { if (write 0 || intervals[write - 1][1] intervals[i][0]) { intervals[write] intervals[i]; } else { intervals[write - 1][1] max(intervals[write - 1][1], intervals[i][1]); } } intervals.resize(write); return intervals; } };这样除了排序本身的栈空间额外空间就是 O(1)。3.4 顺带聊聊不同语言的排序实现差异既然题目标签是“排序”就多聊两句各语言排序实现的差异。我发现不少人在刷题时只关心语言自带的排序怎么调用却没意识到底层实现是不同的。C 的std::sort是不稳定排序复杂度 O(n log n)而std::stable_sort是稳定排序代价是通常需要额外空间。Java 的Arrays.sort对基本类型数组使用双轴快排不稳定对对象数组使用 TimSort稳定。Python 的list.sort()和sorted()都是稳定排序基于 TimSort 实现在部分有序的数据上表现很好最好情况下接近 O(n)。回到这道题排序稳定性其实无所谓因为我们合并时只看左端点左端点相同时右端点在扫描里用max兜底了。但如果你做的是依赖稳定性的题比如“按第二个字段排序后保持第一字段原有的先后顺序”那就要注意语言默认排序稳不稳定了。这个细节在面试里拿出来说是比较加分的点。4. 边界条件与高频坑位提交前先过一遍4.1 边界条件速查表刷题时最烦的是一堆边界条件没想清楚提交一次挂一次。我把这题的边界情况整理了一张表场景输入示例预期输出注意点空数组[][]先判断否则访问intervals[0]直接越界只有一个区间[[1,2]][[1,2]]循环结束后手动 push结果没问题全部重叠[[1,4],[2,3],[1.5,2.5]][[1,4]]右端点必须取 max不能直接赋值完全包含[[1,10],[2,3]][[1,10]]新手最容易错R r会错误缩短区间端点相接[[1,2],[2,3]][[1,3]]力扣判定重叠包含端点判断时用乱序输入[[2,3],[1,4]][[1,4]]必须先排序不然扫描逻辑失效负数区间[[-3,-1],[-2,2]][[-3,2]]比较逻辑对负数同样成立无需特殊处理这张表里的每一种情况我都在本地用一段小脚本测过。特别是“完全包含”这一行基本是提交错误的重灾区。4.2 三个最常见的写错位置第一个错误是忘记排序。输入数据在力扣上往往是乱序的如果直接扫描你会遇到“当前区间已经封口了结果后面又冒出一个左端点很小的大区间”的情况答案全乱。记住这个模板的先后顺序先 sort再扫描顺序不能反。第二个错误是合并时右端点不用max直接写R r。前面说过这会导致大区间被小区间“截断”。这类错误不容易在简单样例上暴露因为像[[1,3],[2,6]]这种用例max(3,6)和直接赋值结果一样但一旦遇到[[1,6],[2,3]]就原形毕露。所以我现在的习惯是所有合并右端点的场景无脑写max不管这个值看起来是不是一定更大。第三个错误是循环结束后忘记把最后一个[L,R]加入答案。因为当前合并区间只有在遇到下一个不相交区间时才会被“落盘”最后一个区间后面没有元素了所以不会触发落盘逻辑。如果忘了补那一次push_back答案会少一个区间。4.3 “相邻区间”到底算不算重叠这个问题值得单独拿出来讲因为很多博客在这上面说法不一。力扣56这道题的官方语义里[1,2]和[2,3]是要合并成[1,3]的测试用例里[[1,4],[4,5]]的输出是[[1,5]]。也就是说判断时用l R是对的。但有些区间问题里比如左闭右开的区间[start, end)端点是允许刚好“无缝衔接”而不是重叠的这时判断条件就要改成l R。做算法题时判断条件到底用还是取决于题目对区间开闭和重叠的定义。做题前先看清楚题面“包含端点”和“不包含端点”会直接影响这一行代码。我在实际面试里被问到过这个细节我的回答是本题默认闭区间端点重合视为重叠所以用如果题目改成了不相交线段需要把重叠定义为“有长度的交集”那判断就改为。这样回答能把灵活性展示出来。5. 从 56 题出发区间问题的通用钥匙5.1 同套路题速查插入区间、无重叠区间、射箭气球、会议室“区间排序 贪心扫描”这个套路在力扣上有一整个家族。我把几个高频的同类题整理成一张表题号题目排序维度贪心策略56合并区间按左端点升序能合并就合并不能合并就落盘57插入区间输入已按左端点排序分成三部分前半段不重叠、插入的区间合并、后半段不重叠435无重叠区间按右端点升序保留右端点尽可能小的区间统计最少移除数量452用最少数量的箭引爆气球按右端点升序每支箭尽量射在区间最右端尽可能多覆盖后面的气球252会议室按开始时间升序判断是否存在同一时刻的会议重叠这几道题放在一起看会发现它们都是“先排序再对相邻区间做一次线性判断”。区别只在于排序维度选左端点还是右端点以及合并条件具体怎么写。练完这五道题区间类算法题基本就通关了一半。这里有个值得思考的点为什么 435 和 452 选择按右端点排序而不像合并区间那样按左端点排序因为这两题的目标是“让区间尽量不相交”按右端点排序后每个区间都能最快地结束让后续区间有更大空间而合并区间的目标是维护当前覆盖面按左端点排序更符合从左往右推进的逻辑。选哪个维度排序取决于题目要保留的边界是哪个方向。5.2 什么时候不该用这个模板讲再多适用场景也得知道边界。如果面试题里出现了下面的情况直接套这个模板就会掉坑第一区间数量固定但查询频繁且每次给出一个新区间要求合并结果。这时候每次排序一遍代价太大更优方案是二分定位插入位置只处理受影响的一段区间这对应的是力扣57插入区间的进阶版。第二区间集合支持动态插入和删除每来一个区间就要维护合并后的完整集合。这种情况用平衡树比如 C 的std::set或线段树更合适因为排序模板无法处理动态变化。第三数据规模极大无法全部加载到内存。这时只能用外排序配合外部归并或者用分布式计算离单机的 O(n log n) 就有距离了。把这些边界讲清楚不只是为了刷题更是为了在真实工程里做“合并时间段”、“合并 IP 段”、“合并配置文件范围”等需求时知道什么方案匹配什么场景。在实际项目中我遇到过合并时间段的需求。数据量并不大但时间段经常是乱序的用这个模板三行搞定。也遇到过要动态加黑名单 IP 段的需求插入频繁排序模板就不适用了我用的是维护一个有序数组加二分插入效果更好。这组对比让我深刻体会到算法模板要会但更重要的是知道模板的适用范围。6. 我刷这道题的一些小习惯6.1 把模板拆成“排序 扫描 收尾”三步记忆很多新手刷题会陷入“一题一解”的误区每道题都从头想刷过就忘。我的做法是给高频模板定制一个固定的“解题三步曲”。对区间合并来说就是排序、扫描、收尾拆成三步之后哪怕过两个月再见到这道题代码也能在五分钟内还原。做题时我会习惯性地给每一步加注释不是为了美观而是为了在面试时能顺着注释讲思路。比如sort(intervals.begin(), intervals.end())上面写一行“按左端点升序将重叠转化为相邻”这样讲代码的时候逻辑是连贯的。6.2 面试时建议先讲贪心正确性再加码细节最后分享一个面试经验。如果在面试中写到这题不要上来直接甩代码先花三十秒讲清楚为什么排序后能 O(n) 扫描。核心表达就是一句话排序后如果当前区间右端点已经小于下一个区间的左端点那它后面不可能再和任何区间重叠因此可以落盘。这一步既能展示你确实理解了算法也能引导面试官往你熟悉的细节上问主动权就掌握在手里。细节方面先把max取右端点、循环后收尾这两个点主动说出来面试官会认为你踩过坑、有工程意识。如果面试官追问“如果端点不算重叠怎么办”再把判断条件从改成这个变体说出来。这样整道题的回答是有层次感的而不是背了一个标准答案。刷题不是比谁背的解法多而是比谁能把一类问题的最优解法讲清楚、写正确、踩过坑。合并区间这道题就是检验你“排序 贪心扫描”这个基础能力的试金石。把这个模板吃透后面遇到整个区间家族都会轻松很多。