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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/merge-k-sorted-interval-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.