LeetCode刷题（python版）——Topic56合并区间

一、题设

以数组 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] 可被视为重叠区间。

二、基本思路

        首先扫一遍题，先将intervals按第一列升序排序，使得相同起点的段连续，再判断能否合并大概有以下三种情况：

         其次我们考虑到每种情况需要做的事情：

         当interval[i][1] < interval[i+1][0]时：此时代表当前段 i 与 之后的无法合并，故直接将intervals[i]加入结果集res中作为另一端的开始即可，但同时要更新结尾end以供下次判断。

        当interval[i][1] >= interval[i+1][0]时：此时代表可以合并，我们将右端变为max(之前结果的右端值，interval[i][1]），左端变为min(之前结果的左端值，interval[i][0])，然后将这两个值预加入结果集中。

三、代码实现

    def merge(self, intervals):
        res = []
        N = len(intervals)
        intervals.sort()# 以intervals[][0]为关键字升序排序
        start,end = -1,-1 # 代表当前结果列表中的开端和结尾
        for i in range(N):
            if intervals[i][0] > end: # 情况一：无交集
                res.append(intervals[i])
                end = intervals[i][1]
            else: # 情况二、三：有交集
                end = max(intervals[i][1],res[-1][1])
                start = min(intervals[i][0],res[-1][0]) # 可省略
                res.pop()
                res.append([start,end])
        return res

四、效率总结