Lintcode577 Merge K Sorted Inter
2018-06-16 本文已影响0人
plai_d75a
【题目描述】
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。这样保持每次取出的节点中是当前最小的，依次加入新的链表，从而得到合并的结果。
【参考答案】
