题目描述

现在有若干个区间，已知这些区间的左右端点（区间包含端点）。

有一些区间是重叠的，可以合并成一个区间，现在请你帮忙完成这一项工作。

输入格式

第一行输入一个正整数 n (0 < n <= ${10}^6$})

接下来输入 n行，每一行包含两个整数 L , R 代表区间的左端点和右端点。（0 <= L <= R<= 2*${10}^9$）

输出格式

对于每组测试用例，首先输出一个数，代表合并后区间个数 m。

然后输出 m 对整数，代表合并之后的区间 (按照左端点递增顺序输出)。

本题讲述的区间是只考虑整数的。例如 区间 [1,5] 和 区间 [6,10] 是可以合并的，因为 5 和 6 之间没有别的数字了。两个区间能否合并的边界条件要具体到题目进行分析，不能一概而论。

样例

4
1 3
2 6
8 10
15 18

3
1 6
8 10
15 18

程序填空

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int L,R;
}x[1000001],ans[1000001];
bool cmp(node i,node j)
{
	return 填空(1); // 按照左端点从小到大排序
}
int main()
{
	int i,n,tot;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d %d",&x[i].L,&x[i].R);
	填空(2); // 排序

	tot = 填空(3); // tot 变量记录最后一共有多少个区间 
	ans[1] = 填空(4); // 最起码有 1 个区间 
	for(i=填空(5);i<=n;i++) // 从第二个区间开始，尽量和前面的一个区间合并。 
	{
		if(x[i].L<= ans[tot].R+1)
			ans[tot].R = 填空(6);
		else
			填空(7);
	}

	printf("%d\n",填空(8));
	for(i=1;i<=填空(8);i++)
		printf("%d %d\n",ans[i].L,ans[i].R); 
	return 0;
}

填空(1) ：{{ input(1) }}

填空(2) ：{{ input(2) }}

填空(3) ：{{ input(3) }}

填空(4) ：{{ input(4) }}

填空(5) ：{{ input(5) }}

填空(6) ：{{ input(6) }}

填空(7) ：{{ input(7) }}

填空(8) ：{{ input(8) }}