合并区间

题目描述

给定若干个区间 intervals[i] = [start_i, end_i]，请合并所有重叠的区间，并输出一个不重叠的区间集合，该集合应当恰好覆盖输入中的所有区间。

如果两个区间有公共部分，或者一个区间的右端点等于另一个区间的左端点，也视为可以合并。

输入格式

第一行输入一个整数 n，表示区间个数。

接下来 n 行，每行输入两个整数 l 和 r，表示一个区间 [l, r]。

输出格式

第一行输出一个整数 m，表示合并后的区间个数。

接下来输出 m 行，每行输出两个整数，表示一个合并后的区间。

按区间左端点从小到大输出。

数据范围

1 <= n <= 10^4

0 <= start_i <= end_i <= 10^4

样例 1

输入

4
1 3
2 6
8 10
15 18

输出

3
1 6
8 10
15 18

样例 2

输入

2
1 4
4 5

输出

1
1 5