Lintcode577 Merge K Sorted Inter

【题目描述】

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

将K个排序的间隔列表合并到一个排序的间隔列表中，你需要合并重叠的间隔。

样例

给定：

[

  [(1,3),(4,7),(6,8)],

  [(1,2),(9,10)]

]

返回

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

【题目链接】

www.lintcode.com/en/problem/merge-k-sorted-interval-lists/

【题目解析】

1. 使用merge sort中的二分的思维，将包含k个链表的列表逐次分成两个部分，再逐次对两个链表合并，这样就有 log(k)次合并过程，每次均使用merge two sorted lists的算法。时间复杂度O(nlog(k))。

2. 使用Priority Queue。这样保持每次取出的节点中是当前最小的，依次加入新的链表，从而得到合并的结果。

【参考答案】

www.jiuzhang.com/solutions/merge-k-sorted-interval-lists/