7620:区间合并
7620:区间合并
总时间限制:1000ms内存限制:65536kB描述
给定 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<iostream>
2 #include<cmath>
3 using namespace std;
4 int ansbegin=10000;
5 int ansend=-1;
6 int beginn[1000001];
7 int endn[1000001];
8 int flag[10000001];
9 int main()
10 {
11 int n;
12 cin>>n;
13 for(int i=1;i<=n;i++)
14 {
15 cin>>beginn[i]>>endn[i];
16 if(beginn[i]<ansbegin)
17 ansbegin=beginn[i];
18 if(endn[i]>ansend)
19 ansend=endn[i];
20 for(int j=beginn[i]*2;j<=endn[i]*2;j++)
21 {
22 flag[j]=1;
23 }
24 }
25 for(int i=ansbegin*2;i<=ansend*2;i++)
26 {
27 if(flag[i]==0)
28 {
29 cout<<"no";
30 return 0;
31 }
32 }
33 cout<<ansbegin<<' '<<ansend;
34 return 0;
35 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录