将区间按起点从小到大排序，然后从左到右扫一遍找最远的右端点，交错或包含的区间就合并。

题目

给出一个区间的集合，请合并所有重叠的区间。

示例

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]

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

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]

解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

考察知识点

数组、排序、图

核心思想

方法一、连通块

直觉

如果我们画一个图，区间看成顶点，相交的区间之间连一条无向边，那么图中连通块内的所有区间都可以合并成一个。

算法

根据上面的直觉，我们可以把图用邻接表表示，用两个方向的有向边模拟无向边。然后，为了考虑每个顶点属于哪个连通块，我们从任意一个未被访问的节点出发，遍历相邻点，直到所有顶点都被访问过。为了效率更快，我们将所有访问过的节点记录在 Set 中，可以在常数时间内查询和插入。最后，我们考虑每个连通块，将所有区间合并成一个新的 Interval ，区间左端点 start 是最小的左端点，区间右端点 end 是最大的右端点。

这个算法显然是正确的，因为这是最暴力的方法。我们对两两区间进行比较，所以可以知道他们是否重合。连通块搜索的原理是因为两个区间可能不是直接重合，而是通过第三个区间而间接重合。例如下面的例子：

1.png

尽管区间 (1,5) 和 (6, 10) 没有直接重合，但是任意一个和 (4, 7) 合并之后就可以和另一个产生重合。图中有两个连通块，我们得到如下两个合并区间：(1, 10) 和 (15, 20)。

时间复杂度：\(O(n^2)\)，建图的时间开销 \(O(V + E) = O(V) + O(E) = O(n) + O(n^2) = O(n^2)\)，最坏情况所有区间都相互重合，遍历整个图有相同的开销，因为 visited 数组保证了每个节点只会被访问一次。最后每个节点都恰好属于一个连通块，所以合并的时间开销是 \(O(V) = O(n)\)。总和为：\(O(n^2) + O(n^2) + O(n) = O(n^2)\)

空间复杂度：\(O(n^2)\)，根据之前提到的，最坏情况下每个区间都是相互重合的，所以两两区间都会有一条边，所以内存占用量是输入大小的平方级别。（不知所云）

方法二、排序方法

直觉

将区间按起点从小到大排序，然后从左到右扫一遍找最远的右端点，交错或包含的区间就合并。

算法

• 使用 lambda 匿名函数，对intervals进行排序，声明保存结果的 result 变量。
• 遍历 intervals。
  • 如果还未曾向 result 中添加过内容（也就是 result 是空的）或者没有任何重叠区间，就添加当前数据。
  • 如果 result 非空，且存在重叠区间，也就是满足合并条件（前一个区间的 end 大于等于后一个区间的start），就合并。
• 返回 reslut。

Python版本

方法二自己的实现（基于递归方法） 不推荐

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        length = len(intervals)
        intervals.sort()
        i = 0
        while i < length:
            tmp_intervals = []
            if i+1 < length and intervals[i][1] >= intervals[i+1][0]:
                tmp_intervals = [[min(intervals[i][0], intervals[i+1][0]), max(intervals[i][1], intervals[i+1][1])]]
                intervals.remove(intervals[i])
                intervals.remove(intervals[i])
                tmp_intervals = tmp_intervals + intervals
                intervals = self.merge(tmp_intervals)
                length = len(intervals)
            else:
                i += 1
            
        return intervals

执行用时 :2304 ms, 在所有 Python3 提交中击败了5.65%的用户
内存消耗 :413.8 MB, 在所有 Python3 提交中击败了5.04%的用户

方法二的高效实现 推荐

class Solution:
    def merge(self, intervals):
        intervals = sorted(intervals, key=lambda x: x[0])  # 使用lambda匿名函数，对intervals进行排序。
        result = []  # 声明保存结果的result变量
        for interval in intervals:  # 遍历intervals
            if len(result) == 0 or result[-1][1] < interval[0]:  # 如果还未曾向result中添加过内容或者是间隔了的区间，就添加当前数据。
                result.append(interval)
            else:  # 如果result非空，且满足合并条件（前一个区间的end大于等于后一个区间的start），就合并。
                result[-1][1] = max(result[-1][1], interval[1])  # 合并方法是选择要合并的两个区间中end较大的那个来作为新区间的end。
        return result  # 返回result

print("leet code accept!!!")
Input = [[[1,4],[2,3]], [[1,4],[0,4]], [[1,3],[2,6],[8,10],[15,18]], [[1,4],[4,5]]]
Answer = [[[1,4]], [[0,4]], [[1,6],[8,10],[15,18]], [[1,5]]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.merge(Input[i])
        print(reslut == Answer[i])

时间复杂度：\(O(nlog\ n)\)，除去 sort 的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的 \(O(nlog\ n)\)。
空间复杂度：\(O(1) (or\ O(n))\)，如果我们可以原地排序 intervals ，就不需要额外的存储空间；否则，我们就需要一个线性大小的空间去存储 intervals 的备份，来完成排序过程。
执行用时 :48 ms, 在所有 Python 提交中击败了82.55%的用户
内存消耗 :13 MB, 在所有 Python 提交中击败了100.00%的用户

有效语法糖

1、Python lambda 函数的用法

lambda 函数也叫匿名函数，及即没有具体名称的函数，它允许快速定义单行函数，类似于C语言的宏，可以用在任何需要函数的地方。这区别于def定义的函数。lambda与def的区别：
1). def创建的方法是有名称的，而lambda没有。
2). lambda会返回一个函数对象，但这个对象不会赋给一个标识符，而def则会把函数对象赋值给一个变量（函数名）。
3). lambda只是一个表达式，而def则是一个语句。
4). lambda表达式” : “后面，只能有一个表达式，def则可以有多个。
5). 像if或for或print等语句不能用于lambda中，def可以。
6). lambda一般用来定义简单的函数，而def可以定义复杂的函数。
7). lambda函数不能共享给别的程序调用，def可以。

lambda语法格式：lambda 变量 : 要执行的语句

# 利用lamda函数，基于dict的key或者value进行排序。
>>> _dict = {1: 100, 3: 25, 2: 50}
>>> sorted(_dict.items(), key=lambda d: d[1])  # 基于value进行升序排列
[(3, 25), (2, 50), (1, 100)]
>>> sorted(_dict.items(), key=lambda d: d[0])  # 基于key进行升序排序
[(1, 100), (2, 50), (3, 25)]