56. 合并区间
3 min
题目
解法：区间合并
思路
核心思想是排序后贪心合并。首先按区间左端点排序，确保处理顺序；然后遍历区间，若当前区间与上一个合并区间重叠则扩展右端点，否则保存当前合并区间并开始新区间。
正确性在于：排序后任意区间只可能与上一个合并区间重叠（因左端点递增），通过比较当前区间左端点与合并区间右端点即可判断重叠。若重叠则更新右端点为较大值（保证覆盖），否则说明无重叠需另起新区间，该贪心策略确保合并后区间最小且无遗漏。
- Step 1: 按区间左端点升序排序
- Step 2: 初始化当前合并区间为第一个区间
- Step 3: 遍历后续区间，若重叠则更新右端点，否则保存当前区间并重置
- Step 4: 遍历结束后保存最后一个合并区间
复杂度
- 时间复杂度: ，主要耗时在排序操作
- 空间复杂度: ，存储结果数组和排序的栈空间
代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
vector<vector<int>>ans;
int l = intervals[0][0];
int r = intervals[0][1];
for(int i = 1 ;i < intervals.size();i++){
if(intervals[i][0] <= r){
r = max(r,intervals[i][1]);
}else{
ans.push_back({l,r});
l = intervals[i][0];
r = intervals[i][1];
}
}
ans.push_back({l,r});
return ans;
}
};