1.题目描述

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

示例 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] 可被视为重叠区间。

2.解题思路

按每个区间的第一个元素由小到大排序，依次比较数组中的前后区间，如果后面区间的头部小于等于前面区间的尾部，则需要合并

弹出前面那个 i 区间，用新生成的区间来更新后面的区间，新生成区间的头部是前后两个区间头部较小值，一定是弹出的区间的头部，因为所有区间按由小到大的顺序排列。新生成区间的尾部一定是前后两个区间尾部较大值

3.代码实现

class Solution(object): def merge(self, intervals): # 正向排序，保证每次把更小的区间弹走 s = sorted(intervals, key=lambda item:item[0]) i = 0 while i+1 <= len(s)-1: #如果后面区间的头部小于等于前面区间的尾部 if s[i+1][0] <= s[i][1]: # 弹出前面那个区间 delet = s.pop(i) # 用新生成的区间来更新后面的区间 s[i][0] = delet[0] # s[i][1]已经是下一个节点的值了，因为前一个已经被弹出去了 s[i][1] = max(delet[1], s[i][1]) else: i += 1 return s