合并区间问题

合并区间

读前福利，送大家一些电子书

问题描述

56. 合并区间

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

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

分析问题

对于任意两个区间A和B，它们之间的关系可以有以下6种情况。


我们将这两个区间进行比较、交换，使得第一个区间的起始位置 ≤ 第二个区间的起始位置这个条件成立，这样的话，我们就可以把这6种情况转换成以下3种。


按照这个思路，我们将所有区间按照左端点进行排序，那么就可以保证任意连续的两个区间，第一个区间的起始位置 ≤ 第二个区间的起始位置，所以他们的关系只有上面三种情况。

算法

对于上面的三种情况，我们可以采用如下算法来求解。

首先，我们用数组 merged 存储最终的答案。然后我们将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：

• 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，即上图中的第二种情况，那么它们不会重合。我们可以直接将这个区间加入数组 merged 的末尾；

• 否则，它们是有重合部分的，即上图中的第一、三种情况，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

这样，我们就可以解决上述的三种情况，下面我们来看一下代码的实现。

class Solution:
    def merge(self, intervals):
        #将区间数组按照左端点进行升序排序
        intervals.sort(key=lambda x: x[0])
        #存放合并后的结果
        merged = []
        for interval in intervals:
            #如果列表为空
            #或者当前区间的左端点大于merged最后一个元素的右端点，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                #否则的话，我们就可以与上一区间进行合并
                #修改merged最后一个元素的右端点为两者的最大值
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

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

空间复杂度是O(logn)。