56. &57 Merge Intervals

题目要求：

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对链表元素按照左边界进行排序
• 然后逐个遍历元素进行大小比较

代码：

# 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)]))