1、将每个区间按照右端点从小到大排序
2、从前往后依次枚举每个区间
如果当前区间中已经包含点,则直接pass
否则,选择当前区间的右端点
#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int N = 100010;
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)
{
scanf("%d %d", &range[i].l, &range[i].r);
}
sort(range, range + n);
int ed = -2e9, cnt = 0;
for (int i = 0; i < n; ++ i)
{
if (ed < range[i].l)
{
cnt ++;
ed = range[i].r;
}
}
printf("%d\n", cnt);
return 0;
}