577. Merge K Sorted Interval Lis

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