Selfish Grazing

这么经典的题目没人写题解（我来水一波）

题目大意：牧场有N头牛，每头牛都有它喜欢的放牧区间[si,Ei]
大多数人都知道母牛很自私。没有牛愿意与其他人共享任何放牧区域。因此，如果Si> = Ej或Ei <= Sj，则两只母牛i和j只能同时放牧。FJ希望知道给定的一组奶牛可以同时放牧的最大奶牛数量及其偏好。

看得很清楚了，就是找到最多不重复子区间，在这之前就要好好想一下贪心策略
我们可以首先让Ei按照从小到大的序列排序
接下来只需要讨论Ei的情况

1. E1<E2 此时s1>s2 不难看出，第二个区间包含第一个区间 这样一来，我们肯定选取区间小的那个，这样会为后面的牛有更多的选择做准备

2. E1<E2 若此时S1<S2 部分包含的关系
   看下图
   你选取得左边得区间越靠向左边 为后面区间争取的空间越大 所以第一个区间保留，第二个区间舍弃的情况是合理的
   综上 除非后面的那个区间的左端大于本区间的右端，否则选择最左端的区间就是最优的

   #include <bits/stdc++.h>
   using namespace std;
   const int maxn=5e4+7;
   struct node {
   int x,y;
   }a[maxn];
   bool cmp(node w,node q)
   {
   return w.y<q.y;
   }
   int  main()
   {
     int n;
     cin>>n;
     for (int i=0;i<n;++i)
     {
       cin>>a[i].x>>a[i].y;
     }
     sort(a,a+n,cmp);
     int r=a[0].y;
     int cnt=1;
     for (int i=1;i<n;++i)
     {
        if(a[i].x>=r)///下个区间
        {
             ++cnt;
             r=a[i].y;///更新右端点
        }  
     }
     cout<<cnt<<endl;
   
   return 0;
   }
   
   

```