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].

解题方法

遇到interval类似的题目总是可以将它们先用comparator sort一下，这里的解法也是这样。

• comparator按照start time sort一下
• 先将第一个interval放到result array里，然后后面的interval不断地与result的末尾Interval merge或者加到末尾

Solution

# 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]
        """
        if not intervals:
            return []

        def compare(a, b):
            return a.start - b.start

        intervals = sorted(intervals, cmp=compare)
        length = len(intervals)

        result = [intervals[0]]
        for i in range(1, length):
            cur = result[-1]
            if cur.end >= intervals[i].start:
                newInterval = Interval(cur.start, max(cur.end, intervals[i].end)) #should choose the max end
                result[-1] = newInterval
            else:
                result.append(intervals[i])
        return result

Reference