一、题目描述

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

示例1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2：

输入：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

作者：力扣 (LeetCode)
链接：leetcode-cn.com/leetbook/re…
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二、题目解析

思路：
直接代码里注释！

三、代码

1.Python实现

初见的第一思路：
1.按左端点从小到大排序

2.有交集，更新右端点；无交集，则保存当前区间

class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

    		//将二维数组intervals按照其内每个子数组第一个元素从小到大排序

        intervals.sort()

        result = list()

        for i in intervals:

            //如果result中没有子数组或者当前两个数组无交集

            //直接保存当前区间

            if not result or result[-1][1] < i[0]:

                result.append(i)

            //否则有交集，取两个数组中第一个元素最大的值作为当前数组的第一个元素（即合并操作）

            else:

                result[-1][1] = max(result[-1][1], i[1])

        return result

复杂度分析

• 
  
• 
  

  时间复杂度：O(n log n)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 O(n log n)。

  
  
  
• 
  

  空间复杂度：O(log n)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(log n) 即为排序所需要的空间复杂度。

  
  
  

2.C实现

留空，等变再牛B点再来手写快排加合并！

3.C++实现

class Solution {

public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        if (intervals.size() == 0) {

            return {};

        }

        sort(intervals.begin(), intervals.end());

        vector<vector<int>> merge;

        for (int i = 0; i < intervals.size(); ++i) {

            int L = intervals[i][0], R = intervals[i][1];

            if (!merge.size() || merge.back()[1] < L) {

                merge.push_back({L, R});

            }

            else {

                merge.back()[1] = max(merge.back()[1], R);

            }

        }

        return merge;

    }

};

🔆In The End！