合并前必须先排序,否则结果不可靠;区间合并依赖左端点升序排列以支持线性扫描判断重叠,C++中常用std::sort配合lambda按a[0]升序排序。

合并前必须先排序,否则结果不可靠
区间合并本质依赖顺序:只有按左端点升序排列后,才能线性扫描并判断是否重叠。C++ 中最直接的方式是用 std::sort 配合 lambda 表达式:
a[0] —— std::sort 要求严格弱序(strict weak ordering),相等时必须返回 false,否则可能触发未定义行为或运行时崩溃(尤其在 libstdc++ 的 debug 模式下会报错)。
intervals[i][0] (当前左端点 ≤ 上一个右端点)- 此时新区间右端点应更新为
std::max(merged.back()[1], intervals[i][1])
常见错误是写成 而非 :比如 [1,4] 和 [4,5] 是相邻而非重叠,但题目中“非重叠区间合并”通常要求将相邻区间也合并(即闭区间语义),所以必须用 。若题意明确要求“严格重叠”,才改用 。
使用 vector> 时避免反复 push_back 引发内存重分配
如果输入规模较大(如十万级区间),合并结果数量远小于输入,频繁 push_back 可能触发多次 vector 扩容。可预先调用:
merged.reserve(intervals.size());
更稳妥的做法是在排序后,用双指针原地覆盖(仅适用于允许修改输入的场景);否则就老实用 reserve,它不改变逻辑,但能稳定提升 10%~20% 性能。
边界情况:空输入、单区间、全重叠需手动验证
这三类容易被忽略,但实际测试常卡在这里:
- 输入
vector→ 输出必须是空>{} vector,不是{{}} - 输入
{{1,2}}→ 直接返回原数组,不能漏掉这个元素 - 输入
{{1,5},{2,3},{4,6}}→ 应合并为{{1,6}},不是{{1,5},{4,6}}
建议在循环前加守卫判断:if (intervals.empty()) return {};,然后初始化 merged 为 {intervals[0]},再从 i = 1 开始遍历——这样比每次检查 merged.empty() 更清晰,也避免分支预测失败带来的微小开销。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











