56. 合并区间

【题目】：56. 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
    	// 按照左端点排序
        sort(intervals.begin(), intervals.end(), [&](vector<int> lhs, vector<int> rhs) {
            return lhs[0] < rhs[0];
        });
        vector<vector<int>> res;
        for(vector<int> interval : intervals) {
            if(res.size() != 0 && interval[0] <= res.back()[1]) {
                res.back()[1] = max(interval[1], res.back()[1]);
            }else {
                res.push_back(interval);
            }
        }
        return res;
    }
};

• 时间复杂度: O(nlogn)
• 空间复杂度: O(n)

先把数组按照左端点排序，这样可以保证可以合并的区间是连续在一起的。
再遍历数组，如果已加入结果数组的最后一个元素的右端点>=当前遍历数组元素的左端点，就进行合并（合并的时候也要注意判断这两个元素的右端点的大小）