AcWing 905. 区间选点
原题链接
简单
作者:
杨某
,
2022-02-18 10:35:15
,
所有人可见
,
阅读 196
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
struct OP{
int l,r;//左右端点
bool operator<(const OP &W)const{
return r<W.r;
}//结构体本身无法比较,重载结构体比较的定义
}op[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
scanf("%d %d",&op[i].l,&op[i].r);
}
sort(op,op+n);//按照右端点排序
int res=0,ac=-2e9;//ac为上一个区间的右端点
//初始化右端点为负无穷,方便取第一个右端点
for(int i=0;i<n;i++){//枚举每一个区间
if(op[i].l>ac){
//当枚举到的区间的左端点严格大于上一个区间的右端点
//证明前面至少需要一个点来覆盖
res++;
ac=op[i].r;//将ac更新为取到的符合条件的区间右端点
}
}
cout<<res<<endl;
return 0;
}