> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/merge-k-sorted-interval-lists.md).

# 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路合并 问题

```python
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
```