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].
Solution
- 按照start 排序
- 然后有重叠时修改ret[-1].end
(Merge-Intervals.py) download
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
29
| # 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]
"""
ret = []
if len(intervals) == 0:
return ret
intervals = sorted(intervals, key = lambda x: x.start)
s = intervals[0].start
e = intervals[0].end
for interval in intervals:
# 第一个interval 或者 没有重叠
if len(ret) == 0 or ret[-1].end < interval.start:
ret.append(interval)
else:
ret[-1].end = max(ret[-1].end, interval.end)
return ret
|