C++怎么实现区间合并_C++重叠区间处理算法【数据】

落涛姑娘_2137

发布时间：2026-03-11 12:14:03

299人浏览过

来源于php中文网

原创

两区间重叠当且仅当a

怎么判断两个区间是否重叠

关键不是看“有没有交集”，而是用不等式避开边界讨论：[a, b] 和 [c, d] 重叠 ⇔ a 。反过来说，不重叠的充要条件是 <code>b ，这个写法能直接绕开开闭区间、端点相等时的各种歧义。

常见错误是写成 a （漏掉等于），结果 <code>[1,2] 和 [2,3] 被判为不重叠——但实际它们在端点 2 处接触，按大多数业务需求（如时间调度、内存段合并）是要合并的。

如果业务明确要求“必须有长度交集”，才用严格小于

输入区间默认满足 left ，否则先做校验或归一化

C++ 中比较 int 没问题，但若含 double，要考虑浮点误差，建议用 std::abs(a - b) 替代直接等号

sort + 一次遍历就能合并，别写嵌套循环

核心思路：先按 left 升序排序，然后线性扫描，维护当前正在扩展的 merged 区间。每次遇到新区间，只和 merged 的右端比较，不用回查前面所有区间。

性能上，O(n log n) 主要花在排序；遍历本身是 O(n)。有人试图用 map 或 set 动态维护，反而引入 O(n log n) 插入开销且逻辑更脆。

立即学习“C++免费学习笔记（深入）”；

C++14
C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

排序时若 left 相同，按 right 降序排（greater），这样相同起点的大区间先被处理，小的会被自然吞掉，少一次合并判断

用 vector<vector>></vector> 存区间？注意 vector 的拷贝成本，大数组建议传引用或用 span（C++20）

原地合并？可以，但需手动管理输出位置索引，易错；推荐新建 result 容器，语义清晰

std::sort 的比较函数怎么写才不出错

别直接写 a[0] 就完事。如果区间是 <code>pair<int int></int>，得用 std::tie 避免手写逻辑漏洞；如果是自定义结构体，必须重载 operator 或传 lambda，且保证严格弱序。

典型翻车点：[1,5], [1,3], [1,8] 排序后变成 [1,5], [1,3], [1,8]（没按右端降序），导致合并出 [1,5] → [1,5]（跳过 [1,3]）→ [1,8]，最终多出一个中间结果。

正确 lambda 示例：[&](const auto& x, const auto& y) { return x[0] != y[0] ? x[0] y[1]; }

用 std::pair？直接 sort(v.begin(), v.end()) 就行，它默认按 first 升序、second 升序——但你要的是 second 降序，所以必须显式传比较器

编译期检查：加 static_assert 确保区间类型可比较，比如 static_assert(std::is_same_v<decltype int>);</decltype>

合并后端点溢出或越界怎么办

如果输入含极大值（如 INT_MAX）或极小值（INT_MIN），合并时 max(right1, right2) 可能不变，但逻辑上没问题；真正危险的是计算型区间（比如由坐标差生成），此时 right = left + len 可能溢出。

不要等运行时报 signed integer overflow ——UB 在 C++ 里不保证报错，可能静默错算。尤其在 LeetCode 类平台，测试数据常故意塞边界值。

用 long long 中转比较，但最终存回 int 前必须检查是否截断（if (val > INT_MAX || val ）

若业务允许，统一用 int64_t 表示端点，省去转换麻烦

STL 算法不帮你防溢出，std::max 对 int 溢出无感知，该崩还是崩

合并逻辑本身很简单，难的是对输入鲁棒性和边界的诚实处理——比如空输入、单区间、全重叠、全不重叠，这些 case 往往比主干逻辑更消耗调试时间。