1236：区间合并
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
给定 n 个闭区间 [ai，bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1，2] 和 [2，3] 可以合并为 [1，3]，[1，3] 和 [2，4] 可以合并为 [1，4]，但是[1，2] 和 [3，4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。
【输入】
第一行为一个整数n，3≤n≤50000。表示输入区间的数量。
之后n行，在第i行上（1≤i≤n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai，bi]（其中 1≤ai≤bi≤10000）。
【输出】
输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。
【输入样例】
5
5 6
1 5
10 10
6 9
8 10
【输出样例】
1 10
1. #include <stdio.h> 2. #include <iostream> 3. #include <string.h> 4. #include <algorithm> 5. using namespace std; 6. int book[10005]; 7. int main(int argc, char *argv[]) 8. { 9. int n,a,b,i,j; 10. scanf("%d",&n); 11. int lt=10005,rt=-5; 12. for(i=1;i<=n;i++){ 13. scanf("%d %d",&a,&b); 14. for(j=a;j<b;j++) 15. if(book[j]==0) book[j]=1; 16. if(a<lt)lt=a; 17. if(b>rt)rt=b; 18. } 19. for(i=lt;i<rt;i++) 20. if(book[i]==0){ 21. printf("no\n");return 0; 22. } 23. printf("%d %d\n",lt,rt); 24. return 0; 25. }
