Description

Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

The intervals in the given list do not overlap.

The intervals in different lists may overlap.

Example

Example1

Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)]

Output: [(1,4),(5,6)]

Explanation:

(1,2),(2,3),(3,4) --> (1,4)

(5,6) --> (5,6)

Example2

Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)]

Output: [(1,2),(3,5),(6,7)]

Explanation:

(1,2) --> (1,2)

(3,4),(4,5) --> (3,5)

(6,7) --> (6,7)

思路：

类似归并排序，只不过在排序过程中要进行区间合并，基本思路是记录合并后数组最后一个区间的end，每次加入新的区间就和end比较决定是否增加一个区间还是连接在原区间之后。

代码：