56 合并区间
以下两种做法思路是一样的,第一种是我自己写的,第二种是别人的题解
我觉得第二种更不容易写错,建议第二种
做法一
这种做法的思路是:
- 对区间左端点进行排序
- 通过取前一个区间的start和end,与当前区间的start和end进行比较,如果当前区间的start比前一个区间的end小,合并当前区间和前一个区间
- 如果当前区间的start比前一个区间的end大,将前一个区间放入答案
我们来思考最后两个区间
当遍历结束到最后一个区间,有两种情况:
- 前一个区间的终点比当前区间的起点大,合并两个区间,
end = max(end,intervals[i][1]); -> 此时合并后的区间没有放入答案 - 前一个区间的终点比当前区间的起点小,将前一个区间放入答案,更新
start = intervals[n - 1][0]和end = intervals[n - 1][1]; -> 此时最后一个区间没有放入答案
因此,我们需要多加一步,将最后的区间放入答案ans.push_back({start, end});
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
// 对区间左端点进行排序
sort(intervals.begin(), intervals.end());
// 前一个区间[start, end]的初始化
int start = intervals[0][0];
int end = intervals[0][1];
vector<vector<int>> ans;
for (int i = 1; i < n; i++) {
// 如果前一个区间的终点比当前区间的起点大,说明要合并两个区间
if (intervals[i][0] <= end)
end = max(end,intervals[i][1]);
// 否则,将前一个区间纳入答案,更新前一个区间[start, end]
else {
ans.push_back({start, end});
start = intervals[i][0];
end = intervals[i][1];
}
}
// 以上处理了前n - 1个区间,还有最后一个区间没有放入答案
ans.push_back({start, end});
return ans;
}
};
做法二
做法二聚焦于当前的区间,前一个区间放在ans的末端(把ans视作栈,ans.back()就是栈顶,通过更新ans.back()完成合并区间)
放入答案的方式是将当前区间放入ans(做法一是将前一个区间放入ans)
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for(auto interval : intervals){
if(!ans.empty() && ans.back()[1] >= interval[0])
ans.back()[1] = max(ans.back()[1], interval[1]);
else
ans.push_back(interval);
}
return ans;
}
};