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)

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