AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
我要出去乱说
,
2021-01-31 13:10:11
,
所有人可见
,
阅读 240
与区间选点问题一模一样
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
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);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (range[i].l > ed) //因为是按右端点排序的,所以不可能会遗漏区间
{
ed = range[i].r;
res ++ ;
}
printf("%d\n", res);
return 0;
}