最开始的想法代码实现(WA):
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),comp);
vector<vector<int>> res;
int size = intervals.size();
if(size == 1)
return vector<vector<int>>{{intervals[0]}};
vector<int> x = intervals[0];
for(int i = 1;i < size;i++)
{
if(x[1] < intervals[i][0])
{
res.push_back({x[0],intervals[i - 1][1]});
x = intervals[i];
}
if(i == size - 1)
res.push_back({x[0],intervals[i][1]});
}
return res;
}
private:
static bool comp(const vector<int>& a,const vector<int>& b) {
return a[1] < b[1];
}
};
与452和435相似都是使用贪心算法,不同的是这里需要按照start排序,同样需要注意的时在接收res.back()时如果不加&,对x修改将无法修改到vector中的内容。这里初始先将排序后的intervals[0]加入到res中,不断的比较修改end的值,当遍历遇到start大于res中的最新end时,直接加入到res中,这样也可能较好的处理最后一个元素。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
int size = intervals.size();
if (size <= 0) return res;
sort(intervals.begin(),intervals.end(),comp);
res.push_back(intervals[0]);
for(int i = 1;i < intervals.size();i++)
{
vector<int>& x = res.back();
if(intervals[i][0] > x[1])
res.push_back(intervals[i]);
else
x[1] = max(x[1],intervals[i][1]);
}
return res;
}
private:
static bool comp(const vector<int>& a,const vector<int>& b) {
return a[0] < b[0];
}
};