区间合并这四个字乍一听像是某种数据处理里顺手就能写完的小工具实际动手才发现它出现的频率高得离谱算法面试里它是最经典的排序加贪心组合工程代码里它被用来归并日志时间段、合并内存碎片、压缩日程冲突。它的核心任务说穿了只有一句话——给一堆可能互相重叠的区间把重叠的部分揉成一块最终得到一组互不相交、按位置排好的干净区间。可就是这么个东西我前后在面试里被问过三四次每次在白纸上重写都还是会先在边界条件上卡一下两个区间端点刚好相接算重叠吗输入是空的怎么办坐标大到开不下数组又怎么处理这篇就把区间合并从头到尾拆开讲思路推演、参考代码、典型例题、踩过的坑全部写清楚不管你是刚开始接触还是已经写过几遍想回头复习细节应该都能捞到点东西。1. 先搞清楚区间合并到底在合并什么1.1 一个看似朴素却容易想歪的需求先给最直接的定义。所谓区间就是一对数字 [l, r]表示从 l 到 r 的这一整段l 叫左端点r 叫右端点。给你一个区间集合比如 [[1,3], [2,6], [8,10], [15,18]]其中 [1,3] 和 [2,6] 有重叠部分 [2,3]所以它们应该被合并成 [1,6]而 [8,10] 和 [15,18] 谁也不挨着谁原样保留。最终输出 [[1,6], [8,10], [15,18]]这就是区间合并的标准结果。这里有个很容易被忽略的隐含要求输出的区间之间不能有任何重叠而且顺序必须是按左端点递增排好的。很多人第一次写的时候只想着把重叠的合起来写完之后发现输出里 [8,10] 排在 [1,6] 前面或者两个本该合并的区间因为顺序问题被漏掉了。所以区间合并的完整定义应该包含两条合并所有有交集的区间同时保证输出有序且互不相交。再往下想一层为什么互不相交这么重要因为互不相交意味着这组区间可以直接用来做二分查找、可以直接做长度求和、可以直接当成一个稀疏的覆盖集合去查询某个点是否被覆盖。如果区间之间还有重叠你算出来的总覆盖长度就会重复计数。这是区间合并最常见的下游用途——它不是终点而是后续查询和统计的前置清洗步骤。1.2 两个区间之间的关系只有三种理解区间合并的关键是先把两个区间之间所有可能的关系穷举清楚。给定区间 A [a1, a2] 和 B [b1, b2]并且假设 a1 b1也就是 A 的左端点不比 B 靠右那么它们的关系其实只有三种关系判定条件合并结果说明完全相离b1 a2保持两个区间A 的右端点在 B 的左端点左边部分相交b1 a2 且 b2 a2[a1, b2]左边界取 A 的右边界取 B 的完全包含b1 a2 且 b2 a2[a1, a2]B 被 A 吞掉左边界和右边界都取 A 的这张表里最有价值的一列是合并结果不管哪种相交情况合并后的左端点都是 a1右端点都是 max(a2, b2)。这就把三种关系里两种情况统一成了一个表达式。也就是说只要判定 b1 a2就说明两者有交集新右边界取两者右端点的较大值。这个结论看起来平平无奇但它正是后面整个算法的支点。我特意把 a1 b1 这个前提写出来因为它解释了一件事为什么必须排序。如果不排序你拿到两个区间得先判断谁在左边才能套用上面这套判断而一旦区间数量上去两两判断的开销就是平方级别。排序的价值在于它一次性把所有谁在左边的问题解决掉让后面的判断可以只看相邻的两个。1.3 无序输入带来的组合爆炸有人会问我能不能不排序直接遍历每个区间跟已有的结果集逐个比对能合并就合并技术上可以但代价是 O(n²) 甚至更高因为每合并一次结果集里的区间可能又要跟别的区间合并你需要反复迭代直到不再发生变化。举个极端点的例子给 10000 个区间每个区间只跟前一个重叠一点点首尾相接成一条长链。用暴力比对的方式每一次插入新区间都要扫描整个结果集总共就是大约 5000 万次比较而排序加扫描只需要先花 O(n log n) 排个序再线性扫一遍总操作量在十几万这个量级。差了三个数量级输入规模再大一点就是能跑和跑不动的区别。所以区间合并的标准解法骨架就定下来了先按左端点排序再用一次线性扫描完成合并。排序把区间在数轴上从左到右整齐排好扫描时只需要维护当前正在拼装的这一块的左右边界遇到能接上的就往后延接不上就把当前这块落盘另起一块。整套流程的时间复杂度是 O(n log n)空间复杂度在不考虑输出数组的情况下是 O(1)。2. 把过程在纸上跑一遍排序加扫描的完整推演2.1 排序键为什么选左端点而不是右端点先说排序这件事本身。最常见的写法是按左端点升序排也就是[1,3]排在[2,6]前面。为什么不是按右端点因为扫描过程中我们要判断的核心问题是下一个区间能不能接上当前这一块。当前这一块的右边界是已知的我们关心的是下一个区间的左端点有没有越过它。左端点有序之后我们只需要一路往后看一旦某个区间的左端点超过了当前右边界后面所有的区间左端点只会更大就更不可能接上了。这个性质让提前结束成为可能也是算法能够线性扫描的根本原因。如果换成按右端点排序判断逻辑就变得别扭你看到右端点大的区间并不知道它的左端点在哪里可能它从很左边就开始也可能只是在很右边的一小段。你可以把算法改成按右端点排的版本但判断条件会绕好几道弯可读性和出错率都不如前者。还有一个细节左端点相同时右端点按什么顺序排标准 C 里pair的默认比较是先比 first 再比 second也就是左端点相同的时候右端点小的排前面。这会不会影响结果不会。因为扫描时我们对右边界取的是max无论小的先来还是大的先来最终右边界都会取到大的那个。但有一个场景例外——如果题目要求你返回合并后的区间并且期望右端点尽量大那么排序顺序本身不影响正确性只是会影响中间状态。所以左端点相同时右端点怎么排都可以图省事就用默认比较。2.2 扫描过程中被维护的那个状态排序完成之后扫描阶段只需要维护两个变量curL和curR表示当前正在拼装的这块区间的左右边界。整个循环的不变量可以理解成每一步都保证为真的事实是这样的在处理第 i 个区间之前[curL, curR] 已经完整包含了前面 i 个区间的全部内容并且它是这 i 个区间能拼出的、包含 i-1 号区间的那一整块。这个不变量听起来有点绕换个说法就清楚了每次拿一个新的区间进来只需要问一句你的左端点有没有越过我的右边界。如果没越过说明两者有交集新的右边界更新为max(curR, 新区间右端点)如果越过了说明新的区间跟当前这块彻底断开当前这块已经完整了可以落盘然后把curL、curR换成新区间的左右端点开始拼新的一块。循环结束后别忘了最后一块。这是新手最容易漏的一步——因为落盘动作是写在else分支里的最后一块永远不会进入else必须在循环外面补一次 push。我自己写这段代码时养成的习惯是只要写了在循环里落盘的逻辑循环外面必定配一句收尾写的时候心里默念一遍能省掉很多无谓的调试。2.3 拿一组数据把每一步摊开看用 [[1,3], [2,6], [8,10], [15,18]] 这组数据完整推一遍。排序后顺序不变依次处理步骤当前块 cur待处理区间判断结果集初始化[1,3]跳至下一项取第一个区间作为起始块[]第 1 次[1,3][2,6]2 3相交curR max(3,6) 6[]第 2 次[1,6][8,10]8 6断开落盘 [1,6][[1,6]]第 3 次[8,10][15,18]15 10断开落盘 [8,10][[1,6],[8,10]]收尾[15,18]无循环结束落盘最后一块[[1,6],[8,10],[15,18]]再看一组能体现包含关系的[[1,10], [2,3], [4,5], [12,13]]。排序后是 [[1,10], [2,3], [4,5], [12,13]]步骤当前块 cur待处理区间判断结果集初始化[1,10][2,3]取首个区间[]第 1 次[1,10][2,3]2 10相交curR max(10,3) 10[]第 2 次[1,10][4,5]4 10相交curR max(10,5) 10[]第 3 次[1,10][12,13]12 10断开落盘 [1,10][[1,10]]收尾[12,13]无落盘最后一块[[1,10],[12,13]]注意第 1、2 步里 curR 完全没有变化这说明被包含的区间在取 max 的时候会被自动吸收掉不需要额外写判断是否被包含的分支。这一点在代码里体现为只用一句curR max(curR, r)就搞定逻辑非常紧凑。2.4 端点相接到底算不算重叠这是区间合并里最有争议的一个点也是面试官最爱拿来追问的点[1,3]和[3,5]能不能合并成[1,5]答案取决于区间的开闭性。如果区间是闭区间[l, r]也就是包含两个端点那么点 3 同时属于两个区间它们是相交的可以合并成[1,5]。如果区间是半开区间[l, r)那么 3 属于前者但不属于后者两者刚好擦肩而过不重叠自然不能合并。还有一种情况是开区间(1,3)和(3,5)中间那个点 3 谁都不包含也不能合并。所以判断条件里的那个不等号是还是完全由题目对区间开闭性的定义决定。现实里绝大多数题目默认闭区间用少数题目会明确说明端点相接不算重叠那就换成。我的建议是写代码之前先把这两个字符确认清楚并且在代码旁边写一句注释因为读到这一段的人包括三个月后的你自己根本没法从反推出题目意图。顺带说一个真实踩坑我有一次做日志时间段合并业务方给的时间段是[start, end)这种半开区间结果我下意识按闭区间写了。本来两段日志在时间上严丝合缝地衔接前一段的结束时间等于后一段的开始时间按业务定义应该保持分开结果被我合成了一大段导致后续按段统计的时候少算了一次切换。小小一个符号排查了快两个小时。3. 参考代码逐行拆解从伪代码到能过的实现3.1 通用伪代码与三个必须记住的点先用伪代码把结构固定下来不管换什么语言骨架都是这一套输入区间列表 intervals 1. 如果 intervals 为空直接返回空结果 2. 按左端点升序排序 3. curL, curR intervals[0] 的左右端点 4. 对 i 从 1 到 n-1 if intervals[i].左端点 curR: curR max(curR, intervals[i].右端点) else: 结果集加入 [curL, curR] curL, curR intervals[i] 的左右端点 5. 结果集加入 [curL, curR] // 收尾 6. 返回结果集三个容易出问题的点我在伪代码里都标出来了。第一是第 1 步的空判断如果没有它第 3 步取intervals[0]就直接越界了而且这个错误在样例上通常不会触发只有提交到空测试用例才炸。第二是第 5 步的收尾前面已经强调过。第三是第 4 步的判断必须用当前块的右边界curR去比而不是用上一个区间的右端点。区别在哪如果用一个被包含的小区间作为参照物比如[1,10]后面跟了[2,3]用[2,3]的右端点去比下一个区间就会误判成断开。这类错误在小数据上很难发现一定要拿一组带包含关系的数据自测。3.2 C 版本pair 默认排序的便利#include bits/stdc.h using namespace std; vectorpairint, int mergeIntervals(vectorpairint, int a) { vectorpairint, int res; if (a.empty()) return res; // 空输入必须先挡掉 sort(a.begin(), a.end()); // pair 默认先比 first再比 second int curL a[0].first, curR a[0].second; for (size_t i 1; i a.size(); i) { if (a[i].first curR) { // 相接视为重叠闭区间用 curR max(curR, a[i].second); // 被包含的情况在这里被自然吸收 } else { res.push_back({curL, curR}); // 当前块已完整落盘 curL a[i].first; curR a[i].second; } } res.push_back({curL, curR}); // 收尾最后一块 return res; }C 用pairint, int的好处是sort默认就按字典序排省掉自己写比较函数的麻烦也就避开了比较函数写错这个坑。参数用值传递vectorpairint,int a是有意的因为内部要排序传引用会把调用方的数据顺序打乱。如果确实不希望发生拷贝可以传const引用然后在函数内部另建一份副本但绝大多数场景下直接值传递更省心。另外注意循环从i 1开始因为第 0 个已经被当作初始块了。3.3 Python 版本显式指定 key 更稳def merge_intervals(intervals): if not intervals: return [] # 显式指定 key避免按元组第二位排序带来的心智负担 intervals.sort(keylambda x: x[0]) res [] cur_l, cur_r intervals[0] for l, r in intervals[1:]: if l cur_r: # 闭区间相接算重叠 if r cur_r: cur_r r else: res.append([cur_l, cur_r]) cur_l, cur_r l, r res.append([cur_l, cur_r]) return resPython 这里有个细节值得说。如果直接intervals.sort()元组会按第一位、第二位依次比较效果上等同于按左端点升序、右端点升序结果其实也是对的。但显式写keylambda x: x[0]有两点好处一是意图明确读代码的人一眼就知道排序依据是什么二是当区间不是元组而是列表、或者结构更复杂比如带权重的区间时默认排序可能会因为元素不可比较而直接报错。我现在的习惯是不管什么语言排序键都写全宁可多敲几个字符。还有一点intervals.sort()是原地排序会修改传入的列表。如果调用方之后还要用原始顺序记得先拷一份intervals[:]。这个坑在函数式风格的项目里踩过不止一次。3.4 Java 版本比较函数别写成减法public int[][] merge(int[][] intervals) { if (intervals null || intervals.length 0) { return new int[0][]; } // 用 Integer.compare不要写 (a, b) - a[0] - b[0] Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] res new ArrayList(); int curL intervals[0][0]; int curR intervals[0][1]; for (int i 1; i intervals.length; i) { if (intervals[i][0] curR) { curR Math.max(curR, intervals[i][1]); } else { res.add(new int[]{curL, curR}); curL intervals[i][0]; curR intervals[i][1]; } } res.add(new int[]{curL, curR}); return res.toArray(new int[res.size()][]); }Java 这段代码里那个比较函数是重点。很多人图省事写(a, b) - a[0] - b[0]在坐标范围不大的时候没问题但如果左端点的取值接近整型边界比如一个是一千多万、另一个是负的一千多万相减就直接溢出结果是负数排序顺序就乱了。Integer.compare内部用的是比较而不是相减不存在这个问题。同理long类型用Long.compare。这个坑平时遇不到一到压测数据或者极端用例上就现形属于典型的知道就没事、不知道就抓瞎。另外toArray那行传了一个new int[res.size()][]作为参数这不是多余的它告诉 JVM 返回数组的确切类型避免内部再做一次类型判断。虽然现代 JVM 上性能差异微乎其微但类型安全上更清晰。4. 例题实战四类变形题的做法4.1 模板题合并所有重叠区间最基础的一题输入一个区间数组要求合并后输出。直接用上面的代码即可需要注意两个常见额外要求一是输出的区间必须按左端点升序这个排序已经保证了二是有些变体要求输出区间的总长度之和那就不要在合并后遍历所有结果区间的长度相加——虽然那样也行但更省事的做法是在合并过程中直接累加每次落盘一块的时候加上curR - curL最后收尾时再补上最后一块的长度。这样省掉一次遍历也避免了长度计算的重复。还有一个小变体是输出合并后的区间个数。这个更简单就是在每次落盘时把计数器加一最后再加一。有经验的人会意识到区间个数实际上等于断开点的数量加一这跟后面的最小覆盖问题有点关系。4.2 变形一插入一个新区间题目给一组已经排好序、互不重叠的区间再给一个新区间要求把新区间插进去并合并。这题有两条路。第一条路是省事的写法把新区间加到原数组末尾然后整体跑一遍标准合并。时间复杂度 O(n log n)能过题但没利用到原数组已经有序这个条件属于浪费。第二条路是充分利用有序性做到 O(n)。做法是把原区间按与新区间的位置关系分成三段完全在新区间左边r newL这些区间跟新区间不相交直接原样输出与新区间有交集l newR r newL这些区间需要跟新区间合并最终合并成一个区间左边界取所有参与合并区间左端点的最小值右边界取所有参与合并区间右端点的最大值完全在新区间右边l newR原样输出。因为原数组已经有序这三段是连续排列的一次遍历就能分完。注意第一段的判断要用严格小于newL第三段的判断要用严格大于newR中间剩下的就是要合并的那一批。这里的严格性很关键如果写成端点相接时就会被错划到左右两段导致漏合并。4.3 变形二最少区间覆盖目标段这题的问法通常是给一组区间和一个目标区间[S, T]问最少的多少个区间可以完全覆盖目标区间覆盖不了就返回 -1。思路是贪心但贪心的方式跟区间合并不完全一样。先把区间按左端点排序然后维护一个当前已经覆盖到的右边界covered初始等于S。每一轮在所有左端点 covered的区间里挑一个右端点最大的用它去拓展covered。如果某一轮找不到任何左端点小于等于covered的区间说明中间出现了断档直接返回 -1。如果某一轮拓展后covered T说明覆盖完成返回使用的区间数。这里最容易写错的是循环的边界控制。因为是一轮里考察一批区间需要用两层循环外层控制轮次内层用指针j扫过所有符合条件的区间。指针j不能在内层循环结束后回退否则复杂度会退化。这个题在我看来是区间类问题里最能检验是否真正理解排序加扫描思想的一道建议自己手写一遍再对照。场景排序键判断条件扫描维护状态标准合并左端点升序l curR当前块左右边界插入区间无需排序已有序与新区间是否相交新区间左右边界最少覆盖左端点升序l covered已覆盖的最右位置无重叠最大化右端点升序l lastEnd上一个选中区间的右端点4.4 变形三不相交区间的最大化选择还有一类题跟区间合并正好相反要求删掉最少的区间让剩下的区间互不重叠。这道题的经典解法是按右端点升序排序而不是左端点。原因很直观右端点越小留给后面区间的空间就越大所以每次贪心地选右端点最小的那个能选就选。这个例子值得单独拎出来说因为它提醒我们区间类问题的排序键没有银弹取决于你贪心的目标是什么。合并问题关心能不能接上所以看左端点选择问题关心留多少空间所以看右端点。我见过不少人在两道题之间直接套模板把排序键换了没换判断条件结果样例能过、隐藏用例全挂。5. 三个最容易翻车的细节与排查思路5.1 排错第一条输出的最后一块去哪了这是区间合并最高频的 bug没有之一。现象是给的测试数据里最后一个区间如果跟前面的合并了结果看起来正常如果最后一个区间是独立的它就从输出里凭空消失了。原因是落盘动作只写在else分支里最后一个区间既没有触发else因为没有下一个区间跟它比较也没有单独收尾。排查方法很简单构造一组数据让最后一块必须独立落盘比如 [[1,2], [5,6]]。如果输出只有 [[1,2]]那就是漏了收尾。修复就是在循环结束后补一句 push。顺带说如果题目要求输出的是合并后的区间个数而不是具体区间这个 bug 表现为数字少了一。所以看到答案差 1 的时候第一反应就该是去检查收尾逻辑。5.2 第二个大坑排序被打乱或者根本没排现象是结果里出现本该合并却没合并的区间而且顺序看着乱。常见原因有三种一是在排序之后又对原数组做了修改破坏了有序性二是排序键写错比如写成了按右端点排但判断逻辑还是按左端点那套三是多线程环境或者共享了同一个数组别人把顺序改了。我的做法是在排序之后、扫描之前加一句调试输出把排序后的序列打出来一眼就能看出排序有没有生效。这一步看起来很笨但比打断点逐步跟踪快得多尤其在做题环境里没有调试器的时候。5.3 第三个大坑坐标范围超出预期如果题目给的坐标范围达到 10^9 甚至更大有两件事必须注意。第一所有跟端点相关的运算都要检查是否会溢出中间量用long long或者 64 位整数更稳妥。第二不要用布尔数组去标记覆盖——这正是很多人下意识想到的暴力涂色法它在坐标小的时候很好用但坐标一大就完全不可行。说到涂色法其实它是一个很好的对拍工具。它的逻辑是开一个布尔数组把每个区间覆盖到的位置全部标记为真然后从左到右扫一遍把连续的标记段输出成区间。这个方法时间复杂度是 O(n * 区间平均长度)只适合小范围数据但胜在逻辑简单、几乎不可能写错。写完正解之后随机生成小范围的区间数据用涂色法作为参考答案对拍几百组能揪出绝大多数边界错误。这个对拍思路我自己用了很多年尤其适合区间、离散化、坐标压缩这一类题目。def brute_force(intervals, max_coord50): 小坐标暴力法仅用于对拍验证区间为闭区间 [l, r] marked [False] * (max_coord 2) for l, r in intervals: for x in range(l, r 1): marked[x] True res [] start None for x in range(max_coord 2): if marked[x] and start is None: start x elif not marked[x] and start is not None: res.append([start, x - 1]) start None return res这个函数配上随机数据生成器基本上十分钟就能把正解的可信度拉起来。数据生成的时候记得让坐标范围小一点比如 0 到 30否则涂色法会很慢同时把区间长度也随机化让长短区间混合出现这样更容易触发包含关系这一类边界。5.4 调试顺序建议真遇到错误的时候我一般按这个顺序排查效率最高先确认空输入和只有一个区间的输入是否正常这能排掉大部分初始化问题再看排序是否生效把排序后的序列打出来检查判断条件用的是不是curR而不是别的变量以及不等号方向检查收尾是否执行最后才怀疑坐标溢出和类型问题。这个顺序的依据是概率从高到低。前面几项是逻辑错误占了绝大多数后面几项是环境问题出现频率低但更难查。6. 从模板题延伸到真实场景里的用法6.1 日程冲突与空闲时间计算日历类应用里判断这个时间段能不能开会本质上就是区间合并加一次查询。把所有已占用时段合并成一组互不相交的区间然后看候选时间段是否落在任何一段里面如果要找空闲时段就是把工作时间和已占用时段做个反向计算——把已占用时段合并然后在工作时间段里挖掉这些块剩下的就是空闲。这里有个业务上的细节会议时段的端点相接通常不算冲突比如一个会议 10:00 结束、另一个 10:00 开始实际是允许的。所以在日程场景里判断条件应该用而不是也就是半开区间的语义。这跟我前面说的端点相接算不算重叠是同一件事只是在不同业务里的答案不一样。6.2 内存段与文件碎片的合并内存管理里有一类常见操作叫空闲块合并当一块内存被释放后如果它的前后邻居也是空闲的就要把它们合成更大的一块避免碎片化。这其实是一个动态版本的区间合并——每次插入或删除一段都要检查相邻块的连续性并合并。它的实现跟静态版本不太一样通常用有序结构平衡树或跳表来维护空闲块插入新块时找前驱和后继判断能否接上能就合并。静态的排序加扫描在这里不适用因为数据在不断变化。但核心的判断逻辑也就是左端点是否小于等于前一块的右边界是完全一致的。理解了静态版本再看这类动态版本就只是数据结构的选择问题。6.3 日志与文本处理中的段落归并处理代码差异或者文本变更记录的时候工具会把有改动的行号区间记录下来。相邻或重叠的改动区域通常在展示前会被合并成一个大块这样阅读体验更好。这跟区间合并是同一个操作把行号区间排序后合并得到若干个独立的变更块。我在处理日志聚合时也遇到过类似需求把同一批请求的时间戳按秒聚合成连续的时间段再统计每个时段内的请求量。这时候区间合并只是前半步后半步是把每个合并后的区间作为分组键去做聚合。用合并后的区间做分组比按固定时间窗口切分要更贴合实际的数据分布——数据密集的地方窗口就短稀疏的地方窗口就长。6.4 什么时候不该用区间合并最后说一个反向的经验。区间合并的前提是这些区间可以被揉成连续的一段因为它默认中间没有空洞。如果业务上需要保留区间内部的空洞信息比如这个时间段内用户在线了 3 次、每次 5 分钟、中间隔了 10 分钟那合并成一个 25 分钟的大段就把信息丢掉了。这种情况下应该保留原始区间列表改用其他统计方式。还有一种情况是区间带有除左右端点之外的其他属性比如每个区间有个权重或者来源标签。合并之后这些属性怎么处理如果不同区间的属性不同合并出来的区间属性就变得没有意义。这时候要么先按属性分组再分别合并要么干脆不合并直接用空间索引结构去回答查询。**判断该不该合并的标准只有一条合并后的区间能不能支撑你后面的查询。**如果合并会丢信息或者下游查询需要原始粒度那就别合。我在实际项目里定这条规则的方式很简单写合并逻辑之前先写下合并后我会拿这组区间去做什么。如果那句话里不需要知道区间的来源和内部结构就放心合并否则就得再想想。