C++区间合并算法详解：从核心原理到LeetCode实战

1. 项目概述为什么区间合并是C程序员必须掌握的基础算法在C的算法世界里尤其是在处理竞赛题、面试题或者实际开发中与时间、空间、坐标相关的业务逻辑时你总会遇到一类问题给你一堆区间让你去合并那些有重叠或相邻的部分。比如合并日程安排、合并IP地址段、合并线段、统计合并后的总覆盖长度等等。这背后就是区间合并算法在发挥作用。它不像动态规划那样复杂也不像图论那样需要庞大的前置知识但它却是检验一个程序员基本功是否扎实、思维是否清晰的“试金石”。很多朋友在初次接触时会觉得这不就是排个序然后遍历一下吗但真上手写边界条件处理不好、逻辑理不顺代码就会写得又臭又长还容易出错。今天我就结合自己十多年的编码和带新人经验把这个看似简单实则暗藏玄机的算法从原理到实现再到实战例题掰开揉碎了讲给你听。无论你是正在准备校招面试、刷题提升还是工作中遇到了类似需求这篇详解都能让你彻底搞懂并写出高效、健壮的代码。2. 算法核心思想与设计思路拆解2.1 问题定义与核心目标首先我们得明确到底要解决什么问题。区间合并算法的输入通常是一个由若干区间组成的集合每个区间由起始点start和终止点end表示例如[1, 3],[2, 6],[8, 10]。这里的区间一般是左闭右闭[start, end]或者左闭右开[start, end)具体取决于题目约定但处理逻辑大同小异。算法的核心目标是将有重叠包括端点相接的区间合并成一个更大的连续区间并返回合并后所有不重叠的区间列表。那么什么是“重叠”这需要精确界定。通常有两种情况完全或部分重叠区间A的结束点大于等于区间B的开始点且区间A的开始点小于等于区间B的结束点。例如[1,5]和[3,7]重叠。端点相接区间A的结束点正好等于区间B的开始点。例如[1,5]和[5,8]通常也视为可合并合并为[1,8]。这一点务必看清题目要求。算法的输出就是合并后的区间集合它们彼此之间没有任何重叠。例如输入[[1,3],[2,6],[8,10],[15,18]]合并后输出[[1,6],[8,10],[15,18]]。因为[1,3]和[2,6]重叠合并为[1,6]。2.2 为什么排序是第一步——贪心思想的体现最直观的暴力解法是两两比较所有区间但时间复杂度是 O(n²)在数据量稍大时比如 n 10⁴就不可接受。区间合并的高效算法O(n log n)核心在于一个预处理步骤对所有区间按照起始点start进行升序排序。为什么要排序这里蕴含了贪心算法的思想。想象一下如果我们把区间画在一条数轴上。如果不排序区间是乱序的比如[8,10],[1,3],[15,18]你很难一眼看出谁和谁可能重叠。排序之后区间按左端点从左到右整齐排列。此时一个关键性质出现了对于排序后的区间列表能够与当前区间合并的区间只可能出现在它的后面并且这些区间一定是连续的。因为后面的区间左端点更大如果它都不能和当前区间合并即它的左端点 当前维护的合并区间的右端点那么更后面的区间左端点更大就更不可能合并了。这让我们可以用一次线性扫描就解决问题无需回头检查。注意排序时如果两个区间起始点相同如何处理结束点通常我们会按起始点升序起始点相同时按结束点升序或降序这里有个小技巧按结束点降序排序有时可以简化逻辑但为了通用性和清晰性我建议起始点相同时按结束点升序排序即可。这保证了扫描时第一个遇到的区间是“最窄”的逻辑更一致。2.3 合并的决策逻辑如何判断与更新排序之后我们维护一个“当前合并区间”curr。然后从第二个区间索引1开始遍历排序后的列表依次与curr比较。 决策逻辑只有两种可能可以合并当遍历到的区间intervals[i]的起始点start_icurr的结束点end_curr。这意味着两个区间有重叠或相接。此时我们不需要新建区间而是扩展curr的右边界curr.end max(curr.end, end_i)。取最大值是因为遍历到的区间可能完全被curr包含例如curr[1,5],intervals[i][2,3]此时右边界不变。无法合并当start_iend_curr。这意味着出现了断层curr已经是一个完整的、无法再与后续区间合并的独立区间了。此时我们将curr加入结果集然后将curr更新为当前遍历到的区间intervals[i]开始新一轮的合并尝试。整个流程就像用一根可以伸缩的橡皮筋去覆盖数轴从第一个区间开始拉长橡皮筋curr遇到能连上的区间就把它拉长到更远的位置更新右端点遇到连不上的区间就把当前橡皮筋的长度记下来存入结果然后从断掉的地方重新开始拉一根新的橡皮筋。3. 核心细节解析与C实现要点3.1 数据结构的选择与表示在C中如何表示一个区间最常用的是std::pairint, int或者std::vectorint。但对于算法题和清晰度而言我强烈推荐自定义一个结构体或类。这虽然多写几行代码但可读性和可维护性大大提升。struct Interval { int start; int end; Interval() : start(0), end(0) {} Interval(int s, int e) : start(s), end(e) {} };如果题目输入是类似vectorvectorint的二维向量我们可以在函数内部将其转换为vectorInterval或者直接操作二维向量但通过索引[0]和[1]访问起止点。为了教学清晰下文将使用Interval结构体。3.2 排序的实现自定义比较函数这是C实现中的第一个关键点。我们需要告诉std::sort如何比较两个Interval对象。方法一定义比较函数推荐给初学者清晰bool cmp(const Interval a, const Interval b) { if (a.start b.start) { return a.end b.end; // 起点相同按终点升序 } return a.start b.start; // 否则按起点升序 } // 使用sort(intervals.begin(), intervals.end(), cmp);方法二重载运算符更C更优雅在结构体内部定义struct Interval { int start, end; // ... 构造函数 bool operator(const Interval other) const { if (start other.start) return end other.end; return start other.start; } }; // 使用sort(intervals.begin(), intervals.end()); // 直接排序方法三使用Lambda表达式C11及以上简洁sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.start b.start; // 通常只按起点排序也足够 });实操心得在绝大多数区间合并问题中只需要按start排序即可无需处理start相同时end的顺序。因为合并逻辑curr.end max(curr.end, next.end)已经包含了这种情况。按start排序保证了扫描的正确性。但如果你追求绝对的严谨或者后续算法需要加上对end的排序也无妨。3.3 合并过程的边界条件与陷阱这是代码最容易出错的地方。我们通过一个具体的实现来剖析vectorInterval merge(vectorInterval intervals) { vectorInterval result; if (intervals.empty()) return result; // 特判输入为空 // 1. 排序 sort(intervals.begin(), intervals.end(), cmp); // 2. 初始化当前区间为第一个区间 Interval curr intervals[0]; // 3. 从第二个区间开始遍历 for (int i 1; i intervals.size(); i) { if (intervals[i].start curr.end) { // 重叠或相接 // 合并更新当前区间的右端点为两者最大值 curr.end max(curr.end, intervals[i].end); } else { // 不重叠将当前区间加入结果 result.push_back(curr); // 更新当前区间为新的区间 curr intervals[i]; } } // 4. 不要忘记最后一个区间 result.push_back(curr); return result; }关键陷阱解析空输入处理第一行的特判是良好习惯防止后续访问intervals[0]导致崩溃。合并条件还是这里使用了意味着将“端点相接”视为可合并如[1,5]和[5,8]合并为[1,8]。如果题目要求相接不合并则条件应改为。务必仔细审题。更新右端点用max这是为了防止“包含”情况。例如curr[1,10],next[2,3]如果错误地写成curr.end next.end就会把区间缩小导致错误。循环结束后补加最后一个区间在循环中我们总是在遇到不重叠的区间时才将curr加入结果。这意味着最后一个curr无论它合并了多少个区间在循环结束时还留在手里必须将其加入结果集。这是新手最容易忘记的一步会导致结果缺失最后一个合并后的区间。3.4 复杂度分析时间复杂度O(n log n)。主要开销在于排序sort的 O(n log n)。之后的线性扫描是 O(n)。所以总体是 O(n log n)。空间复杂度O(log n) 或 O(n)。取决于排序算法是否使用额外空间std::sort通常是原地排序空间复杂度 O(log n) 来自递归栈。结果存储需要 O(n) 空间最坏情况下所有区间都不重叠。通常我们说空间复杂度是 O(n) 或 O(1)如果不算输出存储。4. 实战例题精讲与举一反三光说不练假把式。下面我们看几道经典的LeetCode例题用上面的模板来解决并讲解其中的变体和技巧。4.1 例题一LeetCode 56. 合并区间这是最标准、最经典的模板题。题目描述以数组intervals表示若干个区间的集合其中单个区间为intervals[i] [start_i, end_i]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。示例输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠合并为 [1,6]。直接套用模板输入是vectorvectorint我们只需在循环中稍作调整。vectorvectorint merge(vectorvectorint intervals) { if (intervals.empty()) return {}; vectorvectorint result; // 按左端点排序 sort(intervals.begin(), intervals.end()); // 初始化当前区间为第一个 vectorint curr intervals[0]; for (int i 1; i intervals.size(); i) { if (intervals[i][0] curr[1]) { // 重叠 curr[1] max(curr[1], intervals[i][1]); // 扩展右边界 } else { result.push_back(curr); curr intervals[i]; } } result.push_back(curr); // 加入最后一个区间 return result; }点评这道题就是对我们上面所述算法的直接应用。注意sort对vectorvectorint排序时默认按每个子向量的第一个元素即start升序排列正好符合要求。4.2 例题二LeetCode 57. 插入区间这道题是区间合并的变体难度提升更考验对算法本质的理解。题目描述给你一个无重叠的、按照区间起始端点排序的区间列表intervals和一个新区间newInterval。你需要确保列表仍然有序且不重叠必要时合并区间。示例输入intervals [[1,3],[6,9]], newInterval [2,5] 输出[[1,5],[6,9]] 解释新区间 [2,5] 与 [1,3] 重叠合并为 [1,5]。解题思路 虽然可以先将新区间加入原列表然后调用merge函数但那样时间复杂度是 O(n log n)。由于原列表已排序且无重叠我们可以利用这个性质在 O(n) 时间内完成。遍历原区间列表将所有完全在新区间左侧且无重叠的区间interval.end newInterval.start直接加入结果。遇到第一个与新区间有重叠的区间开始进行合并。合并的逻辑和之前一样newInterval.start min(newInterval.start, interval.start),newInterval.end max(newInterval.end, interval.end)。持续此过程直到遍历到的区间完全在新区间右侧interval.start newInterval.end。将合并后的新区间加入结果。将剩余的完全在新区间右侧的区间加入结果。vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) { vectorvectorint result; int i 0, n intervals.size(); // 1. 加入左侧无重叠区间 while (i n intervals[i][1] newInterval[0]) { result.push_back(intervals[i]); i; } // 2. 合并重叠区间 while (i n intervals[i][0] newInterval[1]) { // 注意条件当前区间起点 新区间终点即重叠 newInterval[0] min(newInterval[0], intervals[i][0]); newInterval[1] max(newInterval[1], intervals[i][1]); i; } // 3. 加入合并后的新区间 result.push_back(newInterval); // 4. 加入右侧无重叠区间 while (i n) { result.push_back(intervals[i]); i; } return result; }点评这道题的关键在于理解“无重叠且已排序”这个条件允许我们进行线性分类处理。它把合并算法的核心——“判断重叠并扩展右边界”——嵌入到了一个更复杂的流程中是检验你是否真正理解合并逻辑的好题目。4.3 例题三LeetCode 228. 汇总区间这道题可以看作是区间合并的“输出格式化”练习或者说是合并思想的另一种应用。题目描述给定一个无重复元素的整数数组nums返回恰好覆盖数组中所有数字的最小有序区间范围列表。示例输入nums [0,1,2,4,5,7] 输出[0-2,4-5,7] 解释区间范围是 [0,2] -- 0-2 [4,5] -- 4-5 [7,7] -- 7解题思路 数组本身可以看作是一系列连续的“点区间”。我们需要找出这些点构成的连续段。初始化一个起始指针start指向当前连续段的开始。遍历数组如果下一个数字不等于当前数字加一即nums[i] ! nums[i-1] 1说明连续中断。将[start, nums[i-1]]这个区间按照格式要求生成字符串加入结果。更新start为新的起点nums[i]。遍历结束后处理最后一个连续段。vectorstring summaryRanges(vectorint nums) { vectorstring result; int n nums.size(); if (n 0) return result; int start nums[0]; // 当前连续区间的起点 for (int i 1; i n; i) { if (nums[i] ! nums[i-1] 1) { // 不连续了 if (start nums[i-1]) { result.push_back(to_string(start)); // 单元素区间 } else { result.push_back(to_string(start) - to_string(nums[i-1])); } start nums[i]; // 开始新的区间 } } // 处理最后一个区间 if (start nums[n-1]) { result.push_back(to_string(start)); } else { result.push_back(to_string(start) - to_string(nums[n-1])); } return result; }点评这道题的本质是寻找“数值上连续”的区间判断条件是相邻元素差值是否为1。它训练的是将合并思想应用于不同场景的能力以及细致的边界输出处理。5. 常见问题排查与性能优化技巧在实际编码和面试中除了写出正确代码你还需要能应对各种边界情况和性能拷问。5.1 典型错误与调试技巧“段错误”或“下标越界”原因没有对输入为空intervals.empty()的情况进行判断直接访问intervals[0]。解决函数开头务必添加空值检查。合并结果遗漏最后一个区间原因在循环中只在“无法合并”时将当前区间加入结果。循环结束后最后一个合并好的区间还保存在curr变量中没有被加入结果。解决在函数返回前记得result.push_back(curr)。合并后区间范围变小原因在合并时错误地将当前区间右端点设置为新区间的右端点curr.end intervals[i].end而没有取两者最大值。解决牢记合并是取并集右端点更新一定是max(curr.end, new.end)。输出区间顺序错误或未排序原因忘记了对输入区间进行排序或者排序的规则不对。解决确认排序规则是按start升序。对于vectorvectorint直接sort即可对于自定义结构体需提供比较函数。5.2 处理大规模数据的考量当区间数量极大例如上百万时O(n log n) 的排序可能成为瓶颈。有没有可能优化如果区间范围有限例如所有区间的起点和终点都在一个已知的、相对较小的范围内比如[0, 10^5]可以考虑使用差分数组或线段树来统计覆盖点最后再扫描生成区间。这种方法时间复杂度可以接近 O(n K)K是值域范围。如果区间本身已部分有序在某些流式数据场景下区间可能按时间等维度大致有序。此时可以考虑使用区间树或二叉搜索树来动态插入和合并每次操作复杂度 O(log n)总体优于每次都全量排序。并行化处理对于超大规模数据可以将区间分片到不同机器或线程上分别进行排序和合并然后再合并各部分的結果。这需要处理跨分片的区间合并问题设计起来更复杂。实操心得对于99%的面试和竞赛场景掌握标准的排序后线性扫描法已经完全足够。只有在面试官特意追问海量数据优化时才需要提及差分数组或线段树等高级数据结构。平时练习首要目标是写出正确、清晰、健壮的代码。5.3 变种问题与思路扩展区间合并的思想可以扩展到多维如矩形合并、带权值如区间调度求最大权重和等问题。区间调度无重叠区间最大数量经典贪心问题。按区间结束时间排序然后选择结束时间最早且不与已选区间重叠的区间。这同样是排序后贪心但排序键和决策逻辑与合并不同。区间交集给定两组已排序的区间列表求它们的交集。双指针遍历核心判断是两个区间是否有重叠部分start max(a.start, b.start),end min(a.end, b.end)如果start end则[start, end]就是一个交集。统计覆盖总长度合并区间后遍历结果列表累加每个区间的长度(end - start 1)即可。这是合并算法的一个直接应用。掌握基础模板后面对这些变种你都能快速识别出核心依然是“排序”和“按顺序处理重叠关系”只是具体的决策条件和目标函数发生了变化。6. 从理论到实践编写健壮且高效的C代码最后我们来整合一下写一个工业级强度的区间合并函数。它应该包含清晰的注释、完善的输入校验、以及方便测试的接口。#include vector #include algorithm #include iostream using namespace std; // 定义区间结构体清晰明了 struct Interval { int start; int end; Interval() : start(0), end(0) {} Interval(int s, int e) : start(s), end(e) {} // 可选重载输出运算符方便调试 friend ostream operator(ostream os, const Interval iv) { os [ iv.start , iv.end ]; return os; } }; class IntervalMerger { public: // 主合并函数处理左闭右闭区间端点相接视为可合并 vectorInterval merge(vectorInterval intervals) { vectorInterval merged; if (intervals.empty()) { return merged; // 返回空向量而非原输入 } // 排序按起点升序起点相同按终点升序非必须但更规范 sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { if (a.start ! b.start) return a.start b.start; return a.end b.end; }); // 初始化当前待合并区间为第一个区间 Interval current intervals[0]; // 遍历后续区间 for (size_t i 1; i intervals.size(); i) { const Interval next intervals[i]; // 判断是否重叠包含端点相接 if (next.start current.end) { // 重叠合并更新当前区间的右边界为两者最大值 current.end max(current.end, next.end); } else { // 不重叠将当前已合并好的区间加入结果 merged.push_back(current); // 从新的区间开始下一轮合并 current next; } } // 至关重要将最后一个合并好的区间加入结果 merged.push_back(current); return merged; } // 一个实用的辅助函数计算合并后区间的总覆盖长度 int totalCoveredLength(const vectorInterval intervals) { int total 0; for (const auto iv : intervals) { total (iv.end - iv.start 1); // 假设为闭区间 } return total; } // 打印区间列表用于调试和验证 void printIntervals(const vectorInterval intervals) { cout [; for (size_t i 0; i intervals.size(); i) { cout intervals[i]; if (i ! intervals.size() - 1) cout , ; } cout ] endl; } }; // 简单的测试用例 int main() { IntervalMerger merger; // 测试用例1标准情况 vectorInterval test1 {Interval(1,3), Interval(2,6), Interval(8,10), Interval(15,18)}; cout 原始区间: ; merger.printIntervals(test1); vectorInterval result1 merger.merge(test1); cout 合并后: ; merger.printIntervals(result1); cout 总覆盖长度: merger.totalCoveredLength(result1) endl; // 测试用例2包含和相接 vectorInterval test2 {Interval(1,4), Interval(4,5), Interval(2,3)}; cout \n原始区间: ; merger.printIntervals(test2); vectorInterval result2 merger.merge(test2); cout 合并后: ; merger.printIntervals(result2); // 测试用例3空输入 vectorInterval test3; cout \n空输入合并后区间数量: merger.merge(test3).size() endl; return 0; }这份代码将核心算法封装在类中增加了计算总长度和打印输出的实用功能并提供了简单的测试。在实际项目中你可能还需要考虑区间类型的泛化使用模板支持long long,double等类型。自定义合并谓词通过函数对象或Lambda让调用者决定何种情况算“重叠”例如间隔小于某个阈值也算。异常安全确保函数在异常情况下资源管理正确。区间合并算法是C算法工具箱中一件小巧但无比锋利的工具。它的核心思想——排序预处理然后线性扫描处理局部重叠关系——是一种非常经典的算法范式。理解并熟练运用它不仅能帮你解决一系列特定的题目更能提升你对贪心算法和线性扫描类问题的直觉。下次遇到需要处理范围、时段、线段的问题时不妨先想想能不能排序能不能合并