题目

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2

  • 0 <= starti <= endi <= 10^4

    解题方法

    贪心

    局部重叠合并，全局个区间不重叠。先对个区间按左端点由小到大排序；在正向遍历区间的时候记录当前重叠段的最左端点和最右端点，当下一个区间的左端点大于记录的最右端点时，将记录值压入结果，更新为当前区间的左右端点并继续遍历。
    时间复杂度O(nlogn)，空间复杂度O(n)（快排的极限空间复杂度）
    C++代码：

    1. class Solution {
    2. public:
    3.   static bool cmp(const vector<int>& a, const vector<int>& b) {
    4.       return a[0]<b[0];
    5.   }
    7.   vector<vector<int>> merge(vector<vector<int>>& intervals) {
    8.       sort(intervals.begin(), intervals.end(), cmp);
    9.       vector<vector<int>> result;
    10.       int left = intervals[0][0];
    11.       int right = intervals[0][1];
    12.       for(int i=1; i<intervals.size(); i++) {
    13.           if(intervals[i][0]>right) {
    14.               result.push_back(vector<int>{left, right});
    15.               left = intervals[i][0];
    16.               right = intervals[i][1];
    17.           }
    18.           right = right > intervals[i][1] ? right :intervals[i][1];
    19.       }
    20.       result.push_back(vector<int>{left, right});
    22.       return result;
    23.   }
    24. };