56. 合并区间
一句话套路按左端排序 + 合并相交区间
题目描述
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3:
输入:intervals = [[4,7],[1,4]] 输出:[[1,7]] 解释:区间 [1,4] 和 [4,7] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
思路
时间
O(n log n)空间
O(log n)思路
按左端点排序后,只需要和「结果里最后一个区间」比:新区间左端 > 上一个的右端 -> 开新段;否则取 max 扩右端。
易错
合并时必须用 max(r, itv[1]),因为存在 [1,10],[2,3] 这种被包含的情况。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
C++17 题解
namespace lc0056 {
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<vector<int>> ans;
for (const auto& itv : intervals) {
if (!ans.empty() && itv[0] <= ans.back()[1])
ans.back()[1] = max(ans.back()[1], itv[1]);
else
ans.push_back(itv);
}
return ans;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0056::Solution s;
vector<vector<int>> a{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
CHECK_EQ(s.merge(a), vector<vector<int>>({{1, 6}, {8, 10}, {15, 18}}));
vector<vector<int>> b{{1, 4}, {4, 5}}; // 端点相接也要合并
CHECK_EQ(s.merge(b), vector<vector<int>>({{1, 5}}));
vector<vector<int>> c{{1, 10}, {2, 3}}; // 包含关系,考验 max
CHECK_EQ(s.merge(c), vector<vector<int>>({{1, 10}}));