合并区间
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1
示例 2
示例 3
模拟答题者思考
1. 最直接：枚举所有区间对的交集关系，用并查集或图连通分量把「能互相重叠到达」的区间归为一组，再每组取 min(start) 和 max(end)——思路正确但实现繁琐，且 O(n²) 判重叠。
2. 重复在哪里？若区间已按起点排序，判断「当前区间是否与已有合并块重叠」只需看 最后一个合并块，不必回溯检查 ans 中更早的区间——因为排序后若与更早块重叠，早就被合并进同一块了。
3. 关键转化：先按 start 排序，再线性扫描。维护 ans 中最后一个区间；若 cur[0] <= ans[-1][1] 说明重叠（含端点相接），扩展右端；否则开新区间。
4. 重叠判定：排序后 cur[0] > ans[-1][1] 即完全不重叠；否则合并。注意 [1,4] 与 [4,5] 中 4 <= 4 算重叠，输出 [1,5]。
5. 复杂度：排序 O(n log n) 主导；扫描 O(n)。空间除输出外主要是排序的 O(log n) 栈。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
intervals | list<list<int>> | 定义：输入的区间集合，每个元素为 [start, end]维护：处理前先按 start 升序排序，保证从左到右扫描时「当前区间起点 ≥ 已处理区间的起点」更新： intervals.sort(key=lambda x: x[0])；排序后线性扫描，不再回退 |
ans | list<list<int>> | 定义：已合并完成的不重叠区间列表（输出结果） 维护：始终按起点递增排列，且相邻区间互不相交 更新：首个区间直接入 ans；后续若与 ans[-1] 重叠则扩展 ans[-1][1]，否则 append 新区间 |
cur | list<int> | 定义：当前正在考察的区间 [start, end]（排序后的 intervals[i]）维护：每次循环取一个尚未并入 ans 的区间，与 ans 末尾比较更新：若 cur[0] <= ans[-1][1] 则重叠，合并；否则 ans.append(cur) |
ans[-1][1] | int | 定义：当前已合并块的最右端点（右边界） 维护：合并时取 max(原右端, cur[1])，因为 cur 可能完全包含在块内也可能向右延伸更新： ans[-1][1] = max(ans[-1][1], cur[1]) |
落码步骤
1. 若 intervals 为空，直接返回空列表
2. 按每个区间的起点 intervals[i][0] 升序排序
3. 初始化 ans = [intervals[0]]
4. 遍历 intervals[1:] 中的每个 cur
5. 若 cur[0] <= ans[-1][1]，重叠：更新 ans[-1][1] = max(ans[-1][1], cur[1])
6. 否则 ans.append(cur)，开始新的合并块
7. 返回 ans
代码实现
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
ans = [intervals[0]]
for cur in intervals[1:]:
if cur[0] <= ans[-1][1]:
ans[-1][1] = max(ans[-1][1], cur[1])
else:
ans.append(cur)
return ansclass Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> ans;
ans.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
auto& cur = intervals[i];
if (cur[0] <= ans.back()[1]) {
ans.back()[1] = max(ans.back()[1], cur[1]);
} else {
ans.push_back(cur);
}
}
return ans;
}
};
// 时间 O(n log n)，空间 O(log n)（排序栈，不计输出）复杂度分析
O(n log n)
O(log n)（排序栈空间，不计输出）
常见坑
忘记排序：输入顺序任意（如示例 3 [[4,7],[1,4]]），不排序就无法用「只看最后一个合并块」的线性策略。
重叠条件写错：本题端点相接算重叠，应是 cur[0] <= ans[-1][1]，不能写成 <，否则 [1,4],[4,5] 无法合并。
合并时只取 cur[1] 而不与 ans[-1][1] 取 max：当 cur 完全落在已有块内部时（如 [1,10] 后跟 [2,3]），右端点会被错误缩短。
必测边界 Case
intervals = [[1,4]] → [[1,4]]（无需合并，直接返回）
intervals = [[1,4],[2,3],[3,6]] → [[1,6]]（排序后依次合并）
intervals = [[1,4],[4,5]] → [[1,5]]（4 <= 4 视为重叠）
intervals = [[1,2],[3,4],[5,6]] → [[1,2],[3,4],[5,6]]（每个区间独立成块）
intervals = [[4,7],[1,4]] → [[1,7]]（排序后与前述逻辑一致）