leetcode 面试经典 150 题：合并区间
| 链接 | 合并区间 |
|---|---|
| 题序号 | 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] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
题解
- 核心思想：
- 排序：首先按照区间的起始点对区间列表进行排序。如果起始点相同，则按结束点排序。
- 遍历合并：遍历排序后的区间列表，依次判断当前区间是否与前一个区间有重叠。如果有重叠，则合并；如果没有重叠，则将前一个区间加入结果列表。
- 处理最后一个区间：遍历结束后，将最后一个区间加入结果列表。
- 复杂度：时间复杂度O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(nlogn)。空间复杂度O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。
- c++ 实现算法：
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// 按照每个区间的起始位置排序
//传入了一个 lambda 函数来定义排序规则。lambda 函数的参数是两个区间 a 和 b，并通过 a[0] < b[0] 比较它们的起始位置。
//sort 函数将按照这个规则将区间按起始位置升序排列。
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> result;//定义二维向量，用于存储最终合并后的区间
// 将第一个区间加入结果
result.push_back(intervals[0]);
//从排序后的第二个区间开始遍历所有区间
for (int i = 1; i < intervals.size(); i++) {
// 获取当前区间和结果中最后一个区间
vector<int> &last = result.back();//result.back() 获取当前 result 中最后一个区间（即最右端的区间）
vector<int> &curr = intervals[i];//intervals[i] 获取当前遍历的区间。我们通过引用获取这两个区间，以便直接修改它们。
// 如果有重叠，更新结果中的最后一个区间
//如果当前区间的起始位置 curr[0] 小于或等于 last 区间的结束位置 last[1]，说明这两个区间有重叠或相邻
if (curr[0] <= last[1]) {
last[1] = max(last[1], curr[1]);
// result.back() = last; //如果不想使用用引用&的方式，则需要加这一行代码，使用 result.back() 更新最后一个区间
} else {
// 如果没有重叠，直接加入当前区间
result.push_back(curr);
}
}
return result;
}
- 算法推演：
输入示例： vector<vector> intervals = {{1, 3}, {2, 6}, {8, 10}, {15,18}};
步骤 1：排序区间 首先，我们对所有区间按照起始位置升序进行排序。排序后的结果是： {{1, 3}, {2, 6}, {8, 10}, {15, 18}} 排序的目的是让重叠的区间靠近，从而方便我们逐一进行合并。
步骤 2：初始化结果 初始化一个 result 向量，并将第一个区间 {1, 3} 放入其中： result = {{1, 3}};
步骤 3：遍历区间 我们遍历排序后的 intervals，从第二个区间开始，逐一与 result 中的最后一个区间进行比较。
第一次迭代（i = 1）： 当前区间 curr = {2, 6}，result 中的最后一个区间 last = {1, 3}。
判断是否重叠：curr[0] (2) <= last[1] (3)，即 2 <= 3，成立，所以这两个区间有重叠。 合并：我们更新
last[1] = max(last[1], curr[1]) = max(3, 6) = 6，所以 last 被更新为 {1, 6}。
更新 result 中的最后一个区间：result.back() = last，所以 result 变为： result = {{1,6}};第二次迭代（i = 2）： 当前区间 curr = {8, 10}，result 中的最后一个区间 last = {1, 6}。
判断是否重叠：curr[0] (8) <= last[1] (6)，即 8 <= 6，不成立，所以这两个区间没有重叠。 直接将当前区间
curr = {8, 10} 添加到 result 中： result = {{1, 6}, {8, 10}};第三次迭代（i = 3）： 当前区间 curr = {15, 18}，result 中的最后一个区间 last = {8, 10}。
判断是否重叠：curr[0] (15) <= last[1] (10)，即 15 <= 10，不成立，所以这两个区间没有重叠。
直接将当前区间 curr = {15, 18} 添加到 result 中： result = {{1, 6}, {8, 10}, {15,18}};步骤 4：返回结果 遍历结束后，result 中存储的就是所有合并后的区间：
result = {{1, 6}, {8, 10}, {15, 18}}; 因此，最终返回的结果是 {{1, 6}, {8, 10}, {15, 18}}，即合并后的区间。
- c++ 完整demo：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// 按照每个区间的起始位置排序
//传入了一个 lambda 函数来定义排序规则。lambda 函数的参数是两个区间 a 和 b，并通过 a[0] < b[0] 比较它们的起始位置。
//sort 函数将按照这个规则将区间按起始位置升序排列。
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> result;//定义二维向量，用于存储最终合并后的区间
// 将第一个区间加入结果
result.push_back(intervals[0]);
//从排序后的第二个区间开始遍历所有区间
for (int i = 1; i < intervals.size(); i++) {
// 获取当前区间和结果中最后一个区间
vector<int> &last = result.back();//result.back() 获取当前 result 中最后一个区间（即最右端的区间）
vector<int> &curr = intervals[i];//intervals[i] 获取当前遍历的区间。我们通过引用获取这两个区间，以便直接修改它们。
// 如果有重叠，更新结果中的最后一个区间
//如果当前区间的起始位置 curr[0] 小于或等于 last 区间的结束位置 last[1]，说明这两个区间有重叠或相邻
if (curr[0] <= last[1]) {
last[1] = max(last[1], curr[1]);
// result.back() = last; //如果不想使用用引用&的方式，则需要加这一行代码，使用 result.back() 更新最后一个区间
} else {
// 如果没有重叠，直接加入当前区间
result.push_back(curr);
}
}
return result;
}
int main() {
vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
vector<vector<int>> merged = merge(intervals);
for (const auto& interval : merged) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
return 0;
}