P1803 凌乱的yyy / 线段覆盖
题目大意
抽象出来，给你\(n\)个线段，统计尽可能多的相互不包含的线段，而分析线段之间的关系，都有三种情况，不相交，相交，包含
当线段之间不包含时，都可以统计为答案的贡献
当线段之间相交时，选取提早结束的就可以尽量多的去统计其他线段
当线段之间包含时，同上，选取尽可能早结束的更优
因此，比较输入的依据是结束时间
#include <algorithm>
#include <iostream>
using namespace std;
int n;
struct segment
{
int begin, end;
};
const int maxn = 1e6 + 5;
segment a[maxn];
bool cmp(segment x,segment y)
{
return x.end < y.end;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i].begin >> a[i].end;
}
sort(a + 1, a + n + 1, cmp);
int ans = 0;
int maxi = 0;
for(int i = 1; i <= n; i++)
{
if(a[i].begin >= maxi)
{
ans++;
maxi = a[i].end;
}
}
cout << ans << endl;
return 0;
}