题目描述

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/merge-intervals

示例：

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

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

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路

1. 排序

本来这是个合并区间的题，但是由于是二维数组，所以得先考虑它的外层，即一维数组之间元素的关系。

所以问题可以简化成外层数组之间每个元素的并集。

那么首先对外层进行排序，依照区间的左端点为基准，即可把每个小区间的起始点有序地排列在数轴上。这样就很容易看出某个区间与它下一个区间是否有交集。

1. 将外层按照左端点排序，并新建一个merged数组用于存放合并后的新区间；
2. 遍历排序后的数组，如果当前区间的左端点在merged数组最后元素的右端点之后，则它们不重合，直接将这个区间加入merged；
3. 否则为重合区间，则取当前区间右端点的值与最后元素右端点值的较大者，更新最后的右端点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        intervals.sort()
        res = [intervals[0]]

        for start, end in intervals[1:]:
            if res[-1][1] < start:
                res.append([start, end])
            else:
                res[-1][1] = max(end, res[-1][1])
        return res

• 时间复杂度: O(nlogn)
• 空间复杂度: O(logn)