Merge K Sorted Interval Lists

Merge_K_sorted interval lists into one sorted interval list. You need to merge overlapping intervals too.

Example

Given

[
  [(1,3),(4,7),(6,8)],
  [(1,2),(9,10)]
]

Return

[(1,3),(4,8),(9,10)]

思路就是用 merge two sorted interval lists 的套路，加上用 heap 的套路来解 k路合并 问题

import heapq
class Solution:
    """
    @param intervals: the given k sorted interval lists
    @return:  the new sorted interval list
    """
    def mergeKSortedIntervalLists(self, intervals):
        # write your code here
        minheap = []
        for i in xrange(len(intervals)):
            if intervals[i]:
                heapq.heappush(minheap, (intervals[i][0].start, intervals[i][0].end, i, 0))

        if not minheap:
            return []

        result = []

        lo, hi = minheap[0][0], minheap[0][1]
        while minheap:
            start, end, i, j = heapq.heappop(minheap)
            # push in next element if available
            if j + 1 < len(intervals[i]):
                heapq.heappush(minheap, (intervals[i][j+1].start, intervals[i][j+1].end, i, j+1))
            # compare start, end with the current interval
            if start > hi:
                result.append(Interval(lo, hi))
                lo, hi = start, end
            else:
                hi = max(hi, end)

        result.append(Interval(lo, hi))

        return result