Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals[1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
. Example 2:
Given[1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
. This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
把一个区间插入一个已排序的无重叠的区间, 如果重叠的话,合并之
方法一:有点类似于快排的方法
1 class Solution(object):2 def insert(self, intervals, newInterval):3 s,e = newInterval.start,newInterval.end4 small = [ i for i in intervals if i.ende ]6 if small + large != intervals:7 s = min(s,intervals[len(small)].start)8 e = max(e,intervals[~len(large)].end)9 return small+[Interval(s,e)]+large
方法二:和上面方法一样,不过这个代码太帅了!!!只需要遍历一次
1 class Solution(object): 2 def insert(self, intervals, newInterval): 3 s,e = newInterval.start,newInterval.end 4 parts = mid,left,right=[],[],[] 5 for v in intervals: 6 parts[(v.ende)].append(v) 7 if mid: 8 s = min(s,mid[0].start) 9 e = max(e,mid[-1].end)10 return left+[Interval(s,e)]+right