最开始的想法代码实现(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];
    }
};