合并区间（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数组的当前填充位置，算法细节见注释。