題目要求：
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].
- 題目要求
解題思路：
- 首先利用key對鏈表元素按照左邊界進(jìn)行排序
- 然后逐個遍歷元素進(jìn)行大小比較
代碼：
# 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].
#
class Interval(object):
def __init__(self, s=0, t=0):
self.start = s
self.end = t
def __repr__(self):
return "[{}, {}]".format(self.start, self.end)
class Solution(object):
def merge(self, intervals):
"""
:param intervals: List[Interval]
:return: List[Interval]
"""
if not intervals:
return intervals
intervals.sort(key=lambda interval: interval.start)
result = [intervals[0]]
for i in range(1, len(intervals)):
pre, current = result[-1], intervals[i]
if current.start <= pre.end:
pre.end = max(current.end, pre.end) # 取其中最大值的值很重要
else:
result.append(current)
return result
if __name__ == "__main__":
print(Solution().merge([Interval(1, 3), Interval(2, 3), Interval(8, 10), Interval(15, 18)]))
