一、题设
以数组 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四、效率总结
