假設(shè)最后返回的vector為merged
首先將整個數(shù)組排序，可以使用c++的sort方法柄冲，按照第一個元素來升序排序放典，代碼如下:
bool cmp(vector<int> a, vector<int> b)
{
if (a[0] == b[0])
{
return a[1] < b[1];
}
return a[0] < b[0];
}
然后所有的區(qū)間對都是升序排列了，這樣有個好處巡社，每次只需取merged的最后一個元素來比較膛堤，如果說第k個區(qū)間的左邊小于merged最后一個區(qū)間的右邊，那它們一定是有相交的重贺，所以可以將他們合并骑祟，反之說明這是兩個不相交的區(qū)間，將第k個區(qū)間壓入數(shù)組气笙。在合并區(qū)間時次企，我犯了一個錯誤潜圃，只是簡單的將第k個的右邊賦值給了，merged最后一個區(qū)間的右邊谭期，但是如果有[1,4].[2,3]的情況，也就是merged最后一個區(qū)間包含了后面的區(qū)間隧出，就會出錯踏志，所以取一個max
整體代碼如下：
bool cmp(vector<int> a, vector<int> b)
{
if (a[0] == b[0])
{
return a[1] < b[1];
}
return a[0] < b[0];
}
class Solution
{
public:
vector<vector<int>> merge(vector<vector<int>> intervals)
{
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (auto interval : intervals)
{
if (interval[0] <= merged.back()[1])
{
merged.back()[1] = max(interval[1], merged.back()[1]);
}
else
{
merged.push_back(interval);
}
}
return merged;
}
};
