每次都拿第i个区间和第i+1个区间比较
if(a[i].r>=a[i+1].l)说明两个区间有交集,并更新i+1的范围;
else ans++ (区间没有重合的,区间加一)
记得最后ans+1(因为开始的默认区间没有加进去)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
#define N 100010
int n,ans;
struct node{
int l,r;
bool operator < (const node &rhs)const{
if(l==rhs.l)return r<rhs.r;
return l<rhs.l;
}
}a[N];
#undef int
int main(){
#define int long long
rd(n);
rep(i,1,n){
rd(a[i].l),rd(a[i].r);
}
sort(a+1,a+n+1);
rep(i,1,n-1){
if(a[i].r>=a[i+1].l){
a[i+1].l=min(a[i].l,a[i+1].l);
a[i+1].r=max(a[i].r,a[i+1].r);
}
else ans++;
}
rep(i,1,n){
printf("%d %d\n",a[i].l,a[i].r);
}
printf("%lld",ans+1);
return 0;
}
# ???
我的题解
为什么你们喜欢把一大堆东西拎出来,放在那里,让人头晕?
有人看得懂吗?