Description
Merge K sorted interval lists into one sorted interval list. You need to merge overlapping intervals too.
Example
Example1
Input: [
[(1,3),(4,7),(6,8)],
[(1,2),(9,10)]
]
Output: [(1,3),(4,8),(9,10)]
Example2
Input: [
[(1,2),(5,6)],
[(3,4),(7,8)]
]
Output: [(1,2),(3,4),(5,6),(7,8)]
思路：
1. 借鉴Merge两个interval的方法，用分治两两合并。
2.用heap实现。Note that if the first elements in a pair of tuples are equal, further elements will be compared when push a tuple in heap.
假设总共有 N 个整数，一共 K 个数组, 时间复杂度 O(NlogK)，空间复杂度 O(K)
代码：
1：
2
网友评论