[LeetCode] Merge Intervals

Very similar to insert intervals.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
"""
Definition of Interval.
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
@param intervals: interval list.
@return: A new interval list.
"""
def merge(self, intervals):
# write your code here
# n log(n)
intervals = sorted(intervals, key=lambda x: x.start)
# + n
i = 1
while i < len(intervals):
if intervals[i].start < intervals[i-1].end and intervals[i].end < intervals[i-1].end:
del intervals[i]
continue
if intervals[i].start <= intervals[i-1].end and intervals[i].end >= intervals[i-1].end:
intervals[i-1].end = intervals[i].end
del intervals[i]
continue
i += 1
return intervals