首页 > 代码库 > Merge Intervals
Merge Intervals
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 = eclass 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
Merge Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。