原题
给出若干闭合区间，合并所有重叠的部分。
样例
给出的区间列表 => 合并后的区间列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
解题思路
- 首先，把区间按照起始点排序
- 然后遍历每一个区间
- 如果result中的最后一个区间的end小于下一个区间的start，则加入下一个区间
- 若大于则update这个
end = max(res[-1].end, interval.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]
"""
intervals = sorted(intervals, key=lambda x:x.start)
res = []
for interval in intervals:
if not res or res[-1].end < interval.start:
res.append(interval)
else:
res[-1].end = max(res[-1].end, interval.end)
return res
