LeetCode 合并区间

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

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

首先，将各个区间按照开始时间升序排列，这样的话，如果相邻区间出现重叠，则一定是前一个区间的结束时间end >= 后一个区间的开始时间start 。

所以，我们首先将interval按照开始时间start进行排序。

接下来，遍历interval，如果是第一个区间直接append入结果res列表；

如果，区间不与res中最后一个区间重叠，则append如res列表；

否则，从res中取出最后一个区间，与当前区间合并后，再append如res列表。

 1 # Definition for an interval.
 2 # class Interval:
 3 #     def __init__(self, s=0, e=0):
 4 #         self.start = s
 5 #         self.end = e
 6 
 7 class Solution:
 8     def merge(self, intervals):
 9         """
10         :type intervals: List[Interval]
11         :rtype: List[Interval]
12         """
13         lenint = len(intervals)
14         if lenint <= 1:
15             return intervals
16         #按照第一个元素进行排序
17         intervals = sorted(intervals, key=lambda inter: inter.start)
18         #遍历第二个元素，如果第二个元素的值比下一个列表的第一个元素的值大，则合并列表
19         res = []
20         for temp in intervals:
21             if len(res) == 0:
22                 res.append(temp)
23             #如果不冲突,直接加入
24             if temp.start > res[len(res)-1].end :
25                 res.append(temp)
26             #如果冲突，进行合并
27             else:
28                 temp2 = res.pop(len(res)-1)
29                 res.append(Interval(temp2.start, max(temp.end, temp2.end)))
30         for temp in res:
31             print(temp.start,temp.end)
32         return res