yicong@algo:~/code/05-array$ cat 0056-merge-intervals.cpp
56. 合并区间
// 思路
两个区间 [a1, a2] 和 [b1, b2](a1 <= b1)能合并的条件是 a2 >= b1, 合并结果是 [a1, max(a2, b2)]。 但如果不排序,任意两个区间都可能重叠,得两两比较,O(n²)。 关键观察:先按左端点排序,那么可能重叠的区间在排序后一定是相邻的 (或者隔着几段已经被前一步合并掉的区间)。于是只需要一趟线性扫描: 从左往右走,维护"当前正在合并的那一段"的右端点 lastEnd: - 如果下一个区间的左端点 <= lastEnd,说明重叠,把它并进来, 右端点更新为 max(lastEnd, 新区间右端点); - 否则不重叠,把当前段收进答案,从新区间重新开一段。 版本一:排序 + 额外结果数组,最直观。 版本二:原地合并,把答案写回原数组再用 resize 截断, 省掉一份 O(n) 的额外结果数组(排序本身还是 O(log n) 栈空间)。
// 时间复杂度
O(n log n),瓶颈在排序;合并那一趟是 O(n)。
// 空间复杂度
版本一:O(n),额外存放结果 版本二:O(1)(不计排序的递归栈和返回值的拷贝),直接在原数组上就地压缩 注意:返回值按值拷贝一份,那部分空间是题目接口决定的,不算算法额外空间。
// 易错点
1. 必须按左端点排序。按右端点排,或者不排,都不对。 2. 判重叠是 <=,不是 <。比如 [1,4] 和 [4,5] 要合并成 [1,5], 写成 lastEnd < intervals[i][0] 会把它俩拆开。 3. 合并时右端点要取 max,不能直接赋值 intervals[i][1]。 反例:[1,10] 和 [2,3],后者的右端点更小,直接赋值会得到 [1,3]。 4. sort 的比较函数参数用 const vector<int>&,不要按值传,否则每次都拷贝。 5. 版本二里合并时用的是 intervals[write-1][1](已经合并过的值), 不能写成 intervals[i-1][1](那是原始的、还没合并的值)。 6. 空输入要能返回空数组;单个区间应原样返回。
// 面试口述要点
1. 先说不排序的两两比较是 O(n²),再说排序后只需一趟扫描; 2. 讲清"排序后可能重叠的区间一定相邻"这个观察,这是 O(n log n) 的根据; 3. 讲清合并条件 a2 >= b1 和右端点取 max 的原因(存在被完全包含的区间); 4. 如果被追问空间,可以给原地版本:答案写回原数组,最后 resize 截断; 5. 顺带提一句:intervals 的元素是 vector<int>,默认的 sort 就是按字典序比, 等价于按左端点排,所以这道题连比较函数都可以不写。但显式写出来更清楚。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:排序 + 额外结果数组
// 按左端点排序后,从左到右一趟扫描,边扫边合并
// ================================================================
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
if (n == 0) {
return {};
}
// 按左端点升序排序
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> ans;
for (int i = 0; i < n; i++) {
if (ans.empty() || ans.back()[1] < intervals[i][0]) {
// 不重叠:把它作为一个新的段放进去
ans.push_back(intervals[i]);
} else {
// 重叠:把右端点扩展到两者的较大值
// 必须取 max,因为可能是 [1,10] 和 [2,3] 这种被完全包含的情况
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
}
}
return ans;
}
// ================================================================
// 版本二:原地合并,省掉结果数组
// 用 write 指向"下一个要写入的位置",答案直接在 intervals 的前 write 个位置里
// 结束时 resize(write) 把尾巴截掉
// 注意:这个函数会修改 intervals
// ================================================================
vector<vector<int>> merge_v2(vector<vector<int>>& intervals) {
int n = (int)intervals.size();
if (n == 0) {
return {};
}
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
int write = 0; // 下一个要写入的位置
for (int i = 0; i < n; i++) {
// write == 0 表示还没有任何一段,先放一段进去
// intervals[write - 1][1] 是"当前正在合并的那一段"的右端点
if (write == 0 || intervals[write - 1][1] < intervals[i][0]) {
intervals[write] = intervals[i]; // 不重叠,开新段
write++;
} else {
// 重叠,扩展当前段的右端点
intervals[write - 1][1] = max(intervals[write - 1][1], intervals[i][1]);
}
}
intervals.resize(write);
return intervals;
}
};
// 本地测试:输入 n,然后 n 对整数(每对是一个区间);每行输出合并后的一个区间
// 同时跑两个版本并比对结果,版本二会改数组所以各用一份副本
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<vector<int>> intervals(n, vector<int>(2));
for (int i = 0; i < n; ++i)
cin >> intervals[i][0] >> intervals[i][1];
vector<vector<int>> copy = intervals; // 给版本二留一份
vector<vector<int>> ans1 = Solution().merge(intervals);
vector<vector<int>> ans2 = Solution().merge_v2(copy);
if (ans1 != ans2) {
cout << "MISMATCH\n";
cout << "v1:";
for (const vector<int>& v : ans1) cout << " [" << v[0] << "," << v[1] << "]";
cout << "\nv2:";
for (const vector<int>& v : ans2) cout << " [" << v[0] << "," << v[1] << "]";
cout << '\n';
return 0;
}
if (ans1.empty()) {
cout << "none\n";
} else {
for (const vector<int>& v : ans1)
cout << v[0] << ' ' << v[1] << '\n';
}
return 0;
}