小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

一、题目描述

以数组 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！

 本博主会持续更新爬虫基础分栏及爬虫实战分栏，认真仔细看完本文的小伙伴们，可以点赞收藏并评论出你们的读后感。并可关注本博主，在今后的日子里阅读更多爬虫文！

如有错误或者言语不恰当的地方可在评论区指出，谢谢！
如转载此文请联系我征得本人同意，并标注出处及本博主名，谢谢 ！