Selfish Grazing

大意就是给出n个线段，让你在n个线段里面选出尽可能多的不相交的线段。
思路：

  ... 1    2    3    4    5    6    7    8    9   10   11   12   13 ...
  ... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1:      <===:===>          :              :              :
Cow 2: <========:==============:==============:=============>:
Cow 3:          :     <====>   :              :              :
Cow 4:          :              :     <========:===>          :
Cow 5:          :              :     <==>     :              :

贪心。
贪心策略：
1.看图可以发现先贪右边界大的区间，如果后面的区间i放不下，也就是和刚选择的区间重合了（选择的区间按题目要求是不重合的，所以和i重合的已选区间就一个），图给我们的灵感是，如果区间i的左边界比已选的大，那么区间i一定比已选的区间更优，要用i替代那个已选区间，也就是给程序一个反悔的机会，替换后的区间依旧互不重合，而且左边的范围更大了，满足局部最优就是全局最优。
2.好像贪心左区间最小的也行。
考虑第一种策略：
1.按右边界降序排序，右边界相同就按左边界升序排序，左边界升序排序是为了减少替换的操作。
2.如果区间i不会和已选区间重合，直接加入。
3.如果区间i会和已选区间重合且比已选区间更优，那么就用i替换掉已选区间。

Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
struct node{
    int x,y;
    bool operator<(const node&a) const{
        if(y==a.y) return x<a.x;
        return y>a.y;
    }
}q[50005];
int main() {
    js; int n,ans=1;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>q[i].x>>q[i].y;
    sort(q+1,q+1+n);
    for(int i=2,pos=1;i<=n;++i) {
        if(q[i].y<=q[pos].x) {
            ++ans;
            pos=i;
        }
        else if(q[i].x>q[pos].x) pos=i;
    }
    cout<<ans<<"\n";
}