合并区间（56）

56. 合并区间 - 力扣（LeetCode）

解法：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() == 1) {return intervals;}//现根据每一项的第一个值，进行排序sort(intervals.begin(), intervals.end(), [](vector<int> & left, vector<int> & right) {return left.front() < right.front();});int cur_left = intervals[0].front();int cur_right = intervals[0].back();int cur_index = 0;for (int i = 1; i < intervals.size(); ++i) {//i项的最小值大于前面已经合并项的最大值，无法继续合并，输出一个新的区间if (intervals[i].front() > cur_right) {intervals[cur_index++] = {cur_left, cur_right};cur_left = intervals[i].front();cur_right = intervals[i].back();}{//和前项的区间合并cur_right = max(cur_right, intervals[i].back());}}//添加最后一个区间intervals[cur_index++] = {cur_left, cur_right};//数据截断intervals.resize(cur_index);return intervals;}
};

总结：

时间计算复杂度O(NlogN)---sort 排序，空间复杂度O(1)，不需要重新构建数组，这里面通过cur_index记录intervals数组的当前填充位置，算法细节见注释。