这道题其实只需要了解题目意思:a[i-1]的右端点和a[i]的左端点有没有交集。如果有,就合并。否则,就输出左端点和右端点。
上代码:
#include<bits/stdc++.h>
using namespace std;
struct s{
int L,R;
};
bool cmp(s x,s y){
return x.L<y.L;
}
s a[500001];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].L>>a[i].R;
sort(a+1,a+1+n,cmp);
int l=a[1].L,r=a[1].R;
for(int i=2;i<=n;i++){
if(a[i].L<=r){
r=max(r,a[i].R);
}else{
cout<<l<<" "<<r<<endl;
l=a[i].L,r=a[i].R;
}
}
cout<<l<<" "<<r;
return 0;
}