合并区间（Merge Intervals）
力扣第 56 题。给一组区间，把所有重叠的区间合并，返回合并后的结果。
核心思路：排序 + 线性扫描
暴力做法是两两比较，O(n²)。最优做法是先排序，排序后重叠的区间一定相邻，就可以一次线性扫描搞定。
最优解法
cpp
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// 1. 按左端点排序
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (auto& cur : intervals) {
// 2. 如果结果集为空，或当前区间与最后一个不重叠，直接加入
if (ans.empty() || cur[0] > ans.back()[1]) {
ans.push_back(cur);
}
// 3. 否则有重叠，合并：右端点取最大值
else {
ans.back()[1] = max(ans.back()[1], cur[1]);
}
}
return ans;
}
为什么排序后只需看”最后一个”？
排序后，区间按左端点从小到大排列。对于当前区间 cur，它只可能与紧邻的前一个发生重叠，不可能跨越去和更早的区间重叠——因为中间的区间左端点更小，如果它们能合并早就合并了。
所以每次只需要看 ans.back() 就够了，不需要回头看。
重叠判断的关键：只看右端点
已有区间: [----] 当前区间: [----] → 重叠，合并 当前区间: [--] → 不重叠，直接加入
重叠条件：cur[0] <= ans.back()[1]（左端点排序后，左端点大小不用担心，只需判断右端点）
合并时右端点取 max，是为了处理被完全包含的情况：
已有区间: [----------] 当前区间: [----] → cur[1] < ans.back()[1]，右端点不能缩小
走一遍例子
输入: [[1,3],[2,6],[8,10],[15,18]] 排序后（已有序）: [[1,3],[2,6],[8,10],[15,18]] 处理 [1,3]: ans 为空，加入 → ans = [[1,3]] 处理 [2,6]: 2 <= 3，重叠，右端点取 max(3,6)=6 → ans = [[1,6]] 处理 [8,10]: 8 > 6，不重叠，加入 → ans = [[1,6],[8,10]] 处理 [15,18]: 15 > 10，不重叠，加入 → ans = [[1,6],[8,10],[15,18]]
复杂度
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(n log n) | 瓶颈在排序，扫描是 O(n) |
| 空间 | O(1) | 不算输出的话，原地操作 |
这道题不能做到 O(n)，因为必须排序——排序的 O(n log n) 下界无法突破（除非输入已有序）。
一个变体要注意
插入区间（力扣 57 题）：给一个已排序且不重叠的区间列表，插入一个新区间，返回合并后结果。思路是把新区间直接插入后调用 merge，或者更优雅地分三段处理（新区间左边不重叠的、重叠需合并的、右边不重叠的），O(n) 解决。掌握了本题再做 57 题就是水到渠成。