原題
給出若干閉合區(qū)間，合并所有重疊的部分蚌卤。
樣例
給出的區(qū)間列表 => 合并后的區(qū)間列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
解題思路
- 首先奥秆，把區(qū)間按照起始點(diǎn)排序
- 然后遍歷每一個(gè)區(qū)間
- 如果result中的最后一個(gè)區(qū)間的end小于下一個(gè)區(qū)間的start，則加入下一個(gè)區(qū)間
- 若大于則update這個(gè)
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
