AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
_如鲸向海
,
2022-06-04 22:37:17
,
所有人可见
,
阅读 115
C++ 代码
/*可以按前一题的方式将所有区间分为几个集合,每个集合中各个区间都至少有一点相交。若要选取不相交两个区间
,那么两个区间必定处于不同的集合中,而最大的不相交区间数量便是总集合数,也就是区间选点的数量。所以两题代码相同。*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
PII p[N];
bool comp(PII a,PII b){
return a.second<b.second;
}
int main(){
int number;
cin>>number;
int pointnum=0;
for(int i=0;i<number;i++){
cin>>p[i].first>>p[i].second;
}
sort(p,p+number,comp);
int maxr = -0x3f3f3f3f;
for(int i = 0;i<number;i++){
if(p[i].first>maxr){
pointnum++;
maxr = p[i].second;
}
}
cout<<pointnum<<endl;
}