[文章目录]
Description
约翰有N(1≤N≤50000)头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间(Si，Ei)吃草，1≤Si<Ei≤1,000,000,00.奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意两头牛都不会共享他们喜欢吃草昀领域．如果奶牛i和奶牛J想要同时吃草，那么要满足：Si>=Ej或者Ei≤Sj．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？
贪心策略好像应该是将r从小到大排序，然后直接扔就好了，举不出反例。
然而我的方法是将包含其他区间的区间都先踢出去，然后从左向右选。感觉挺容易想的吧。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ans,top;
struct node {int l,r;};
node a[50100],z[50100];
bool cmp(node x,node y){return x.l==y.l?x.r>y.r:x.l<y.l;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
while(top&&z[top].r>=a[i].r) top--;
z[++top]=a[i];
}
int now=0;
for(int i=1;i<=top;++i)
if(z[i].l>=now) now=z[i].r,ans++;
printf("%d",ans);
return 0;
}