AcWing 905. 区间选点
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-20 09:07:12
,
所有人可见
,
阅读 221
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range {
int l, r;
bool operator< (const Range &W)const {
//此时是按照右端点来进行排序
return r < W.r;
}
}Range[N];
int main() {
scanf("%d", &n);
//将区间读入
for (int i = 0; i < n; i ++) {
int l, r;
scanf("%d%d", &l, &r);
Range[i] = {l, r};
}
sort(Range, Range + n);
//从左往右进行扫描
//res表示此时已经选中的点的个数
//ed表示的是上一个点的坐标, 由于对于第一个点是没有上一个点的, 所以初始化为负无穷
int res = 0, ed = -2e9;
//枚举所有的区间
for (int i = 0; i < n; i ++) {
//如果此时区间的左端点是严格大于ed, 此时选择当前区间的右端点
if (Range[i].l > ed) {
res ++;
ed = Range[i].r;
}
}
printf("%d", res);
return 0;
}