AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
心有远方从未止步
,
2022-09-23 19:49:06
,
所有人可见
,
阅读 128
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
struct Segment
{
int l, r;
bool operator < (const Segment& t) const
{
return r < t.r;
}
}seg[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d %d", &seg[i].l, &seg[i].r);
sort(seg, seg + n); //排序,默认按结构体前面的数据排序
int ans = 0, last = -2e9;
for(int i = 0; i < n; i ++)
{
if(last < seg[i].l) //直接判断边界,前面的右端点小于后面的左端点,即ans加一
{
ans ++;
last = seg[i].r;
}
}
cout << ans << endl;
return 0;
}