题目
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
例：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
方法
思路与 435. 无重叠区间类似，只不过本题需要合并重复区间
- 对区间集合按照区间的下标为零的位置的数字大小按照从小到大进行排列
- left 表示此时区间的最左边界下标，初始值为第一个区间的 starti；right 表示此时区间的最右边界下标，初始值为第一个区间的 endi；result 表示合并重叠区间后的区间集合
- 循环区间集合。
若区间的起始值 intervals[i][0] 小于等于前一个区间的结束值或更新后区间的最右边界值 right，表示两个区间重叠，同时，若区间的结束值 intervals[i][1] 大于前一个区间的结束值或更新后区间的最右边界值 right，表示两个区间存在重叠部分但是也存在不重叠部分，那么更新最右边界值 right。
若区间的起始值 intervals[i][0] 大于前一个区间的结束值或更新后区间的最右边界值 right，表示两个区间不重叠，那么将前一个区间的（新）起始值和（新）结束值加入 result，并更新区间的最左边界和最右边界 - 因为每次的将区间的左右边界加入 result 是滞后的，所以最后一个区间在更新后无法在循环里加入，所以需要单独加入
class Solution(object):
def merge(self, intervals):
intervals.sort(key = lambda x:x[0])
left, right = intervals[0][0], intervals[0][1]
result = []
for i in range(1, len(intervals)):
if intervals[i][0] <= right:
if intervals[i][1] > right:
right = intervals[i][1]
else:
result.append([left, right])
left, right = intervals[i][0], intervals[i][1]
result.append([left, right])
return result
