Problem: 56. 合并区间

题目描述

思路及解法

1.将数组按内部的一维数组的第一项按从小到大的顺序排序；
2.创建二维结果数组merged，并将排序后的数组中的第一个一维度数组存入到merged中；
3.从后面的一维数组开始遍历，并比较：

3.1 若后面一个一维数组的左侧值大于merged中的一维数组的右侧值，则直接将当前的一维数组添加到merged中；
3.2 若后面一个一维数组的左侧值小于merged中的一维数组的右侧值，则取出右侧值较大的合并

复杂度

时间复杂度:

$O(nlogn)$；其中$n$为一维数组的个数

空间复杂度:

$O(n)$

Code

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            if (merged.empty() || merged.back()[1] < left) {
                merged.push_back({left, right});
            } else {
                merged.back()[1] = max(merged.back()[1], right);
            }
        }
        return merged;
    }
};