Leetcode 56.合并区间

题目描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 $intervals[i] = [start_i, end_i]$ 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

1
2
3

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• $1 <= intervals.length <= 10^4$
• $intervals[i].length == 2$
• $0 <= starti <= endi <= 10^4$

链接：

https://leetcode-cn.com/problems/merge-intervals

题目分析

  可以合并的区间存在着这样的性质：假设左端点靠左的区间为 interval_1，左端点靠右的区间为 interval_2，则有 interval_1->end >= interval_2->start，也即存在重叠。则如果我们按照区间的左端点大小进行排序，则可以进行合并的区间一定是连续的。
  声明一个 result 数组作为结果返回，我们先将第一个区间加入结果。之后对于后面的每一个区间，我们有这样的操作：如果该区间和 result 中的最后一个区间不存在重合（满足 intervals[i]->start > result[count]->end），则将其作为新区间加入到 result 中；若该区间与 result 中的最后一个区间重合，则更新 result 的最后一个区间，变成合并后的结果，也即 result[count]->end = max(result[count]->end, intervals[i]->end)。顺序遍历所有的区间后得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        int count = -1;

        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < intervals.size(); i++){
            if(result.empty() || intervals[i][0] > result[count][1]){
                result.push_back({intervals[i][0], intervals[i][1]});
                count++;
            }
            else{
                result[count][1] = max(result[count][1], intervals[i][1]);
            }
        }
        return result;
    }
};

  时间复杂度：$O(n\log n)$，其中 $n$ 为区间的个数。对所有的区间进行排序需要 $O(n\log n)$ 的时间，而排序后只需要一次遍历，也即 $O(n)$ 的时间，因此总的时间复杂度为 $O(n\log n)$。
  空间复杂度：$O(\log n)$，其中 $n$ 为区间的个数。作为答案返回的数组不计入所需空间，则所需的额外空间也即排序所需要的空间。