Merger Intervals

Question

Given a collection of intervals, merge all overlapping intervals.

Example Given intervals => merged intervals:

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]

Challenge O(n log n) time and O(1) extra space.

Thoughts

方法1 利用insert intervals

方法2 先sort,再一个一个处理

Solution

方法1

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def __init__(self):
        self.results = []

    def merge(self, intervals):
        # write your code here
        results = []
        for inter in intervals:
            results = self.insert(results, inter)
        return results

    def insert(self, intervals, newInterval):
        results = []
        insertPos = 0
        length = len(intervals)
        for i in range(length):
            cur = intervals[i]
            if cur.end < newInterval.start:
                results.append(cur)
                insertPos += 1
            elif cur.start > newInterval.end:
                results.append(cur)
            else:
                newStart = min(cur.start, newInterval.start)
                newEnd = max(cur.end, newInterval.end)
                newInterval.start = newStart
                newInterval.end = newEnd
        results.insert(insertPos, newInterval)

        return results