思路
大家应该都感觉到了,此题一定要排序,那么按照左边界排序,还是右边界排序呢?
都可以!
那么我按照左边界排序,排序之后局部最优:每次合并都取最大的右边界,这样就可以合并更多的区间了,整体最优:合并所有重叠的区间。
局部最优可以推出全局最优,找不出反例,试试贪心。
那有同学问了,本来不就应该合并最大右边界么,这和贪心有啥关系?
有时候贪心就是常识!哈哈
按照左边界从小到大排序之后,如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界,则一定有重复,因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
即:intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内,那么一定有重复!
这么说有点抽象,看图:(「注意图中区间都是按照左边界排序之后了」)
知道如何判断重复之后,剩下的就是合并了,如何去模拟合并区间呢?
其实就是用合并区间后左边界和右边界,作为一个新的区间,加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
写法一
class Solution {
public:
static bool cmp(vector<int> a,vector<int> b){
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
vector<vector<int>> res;
int Maxright=intervals[0][1];
int ii=0;
for(ii=1;ii<intervals.size();ii++){
if(intervals[ii][0]<=Maxright){
Maxright=max(intervals[ii][1],intervals[ii-1][1]);
intervals[ii][0]=min(intervals[ii-1][0],intervals[ii][0]);
intervals[ii][1]=max(intervals[ii-1][1],intervals[ii][1]);
}else {
res.push_back(intervals[ii-1]);
Maxright=intervals[ii][1];
}
}
res.push_back(intervals[ii-1]);
return res;
}
};
写法二
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.size() == 0) return result;
// 排序的参数使用了lamda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) { // 合并区间
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
};
时间复杂度:O(nlogn) ,有一个快排
空间复杂度:O(1),不算result数组(返回值所需容器占的空间)