51nod 1133 不重叠的线段

简单的贪心算法，类似于活动安排的思想，为了选择尽可能多的线段，应该选择终点小的线段

首先把线段按照终点排序，依次选择不重叠的线段，就可以安排可能多的线段了

最优子结构性质:
假如选择了第一个，那么就要在余下的时间里选择最多的选择

贪心选择:
选择终点早的线段，可以使得选择的线段尽可能多，这就是贪心选择

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct line{
    long long int start;
    long long int ends;
}line;

bool cmp(line a,line b)
{
    if(a.ends<b.ends)
        return true;
    else if(a.ends==b.ends&&a.start<b.start)
        return true;
    return false;
}

int main()
{
    int n;
    cin>>n;
    line all[10005];
    for(int i=0;i<n;i++)
        cin>>all[i].start>>all[i].ends;
    int cnt=1;
    sort(all,all+n,cmp);
    int lastend=all[0].ends;
    for(int i=1;i<n;i++)
    {
        if(all[i].start>=lastend)
        {
            lastend=all[i].ends;
            cnt++;
        }
    }
    cout<<cnt<<endl;
}