区间合并（计蒜网）
蒜头君给定 nn 个闭区间 [a_i, b_i] [a i,b i ]，其中 i=1,2,…,ni=1,2,…,n。
任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1,2][1,2] 和 [2,3][2,3] 可以合并为 [1,3][1,3]，[1,3][1,3] 和 [2,4][2,4] 可以合并为 [1,4][1,4]，但是 [1,2][1,2] 和 [3,4][3,4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出 “no”。
输入格式 第一行为一个整数 nn，3 \le n \le 500003≤n≤50000。表示输入区间的数量。 之后 nn 行，在第 ii 行上（1 \le i \le n1≤i≤n），为两个整数 a_ia i 和 b_ib i ，整数之间用一个空格分隔，表示区间 [a_i, b_i][a i,b i ]（其中 1 \le a_i \le b_i \le 100001≤a ≤b i ≤10000）。 输出格式 输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 “no”。
输出时每行末尾的多余空格，不影响答案正确性
思路：详细见代码，用到了pair,然后有交叉就能合并
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> p1,pair<int,int> p2){
if(p1.first!=p2.first){
return p1.first<p2.first;
}else{
return p1.second<p2.second;
}
}
int main(){
//有交叉就可以合并
pair<int,int> a[50010];
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i].first>>a[i].second;
}
sort(a,a+n,cmp);
pair<int,int> t=a[0];
bool flag=true;
for(int i=1;i<n;i++){
if(a[i].first <= t.second && t.second<=a[i].second){
t.second=a[i].second;
}else if(t.second < a[i].first){
flag=false;
break;
}
}
if(flag==false){
cout<<"no"<<endl;
}else{
cout<<t.first<<" "<<t.second<<endl;
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-04-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读