提交时间:2019-11-09 18:42:11

运行 ID: 2157

#include<iostream> using namespace std; int n,begin1[1001],end1[1001]; void init(){ cin>>n; for(int i=1;i<=n;i++) cin>>begin1[i]>>end1[i]; } void qsort(int x,int y){ int i,j,mid,t; i=x;j=y;mid=end1[(x+y)/2]; while(i<=j){ while(end1[i]<mid) ++i; while(end1[j]>mid) --j; if(i<=j){ t=end1[j];end1[j]=end1[i];end1[i]=t; t=begin1[j];begin1[j]=begin1[i];begin1[i]=t; ++i;j--; } } if(x<j) qsort(x,j); if(i<y) qsort(i,y); } void solve(){ int ans=0; for(int i=1,t=-1;i<=n;++i) if(begin1[i]>=t){ ++ans;t=end1[i]; } cout<<ans<<endl; } int main(){ init(); qsort(1,n); solve(); return 0; }