Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
这题和Insert Interval类似,但是难度要低.主要在于我们可以先对全部区间做排序.区间开头已经排完序后, 则后加入的区间b相比于开始的区间a, b.start >= a.start. 判断重合则只需要b.start <= a.end.
代码如下:
# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ #sweep line if not intervals: return [] intervals.sort(key = lambda x: (x.start,x.end)) res = [intervals[0]] for inter in intervals[1:]: if inter.start > res[-1].end: #不重合 res.append(inter) else: #有重合 if inter.end > res[-1].end: res[-1].end = inter.end return res
原文：http://www.cnblogs.com/sherylwang/p/5818664.html