56：合并区间

问题描述

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

样例

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

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

问题分析

一个朴素的想法就是将区间按照left值排序，然后遍历它看看能不能合并。
具体怎么看呢？我们排序之后可以保证如果下一个元素的left值比上一个元素的right值要小，那么它必然是重叠了一部分，至于右边界的话就要看max_right与下一个区间的right值哪个大了。记得更新right值。
我们这样弄，由于写程序的实现不同，我们可能会出现漏掉最后一个长区间的情况，咋办？我们可以对它进行单独处理。

AC代码：

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x:x[0])
        res = []
        left = right = None
        for i in range(len(intervals)):
            if left is None:
                left = intervals[i][0]
                right = intervals[i][1]
            if i+1 < len(intervals) and right >= intervals[i+1][0]:
                right = max(right,intervals[i+1][1]) # 更新right值
            else:
                res.append([left,right]) # 此长区间结束了，加到结果集
                left = None
        if left is not None: # 对最后一个合法长区间进行处理
            res.append([left,right])
        return res
s = Solution()
print(s.merge([[1,4],[2,3]]))