2018-11-06-poj-2376

题目:POJ-2376
对左端点升排序，如果左端点相等，按右端点降序排序，这保证左端点一定被覆盖，求出从左端点开始能够被覆盖的最大值(从开头到当前位置)，然后不断跳跃前进。可以证明
跳跃前进时不会重复，因为最小值和最大值可能不是同一头牛，但是没有关系，选择最大值的那头就可以了，如果最大值那头牛被选中过，现在应该已经跳过去了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

struct cows
{
    int s,e;
};

const int N = 25000;

int cmp(struct cows a1,struct cows a2)
{
    if(a1.s < a2.s)
        return 1;
    if(a1.s > a2.s)
        return 0;
    if(a1.e > a2.e)
        return 1;
    if(a1.e <= a2.e)
        return 0;
    exit(1);
}

int main(void)
{
    int n,t;
    struct cows a[N];
    int i,j,maxi,cnt;
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d%d",&a[i].s,&a[i].e);
        sort(a,a+n,cmp);
        for(i=1,j=1,maxi=a[0].e;i<n;i++)
        {
            if(a[i].s != a[i-1].s)
            {
                a[j] = a[i];
                if(maxi <= a[j].e)
                    maxi = a[j].e;
                else
                    a[j].e = maxi ;
                j++;
            }
        }
        for(n=j,i=1,j=0,cnt=0;i<=t&&j<n;j++)
        {
            if(i < a[j].s)
            {
                cnt = -1;
                break;
            }
            else
            {
                for(;j<n&&a[j].s<i;j++);
                if(j == n || a[j].s > i)
                    j--;
                cnt++;
                i = a[j].e + 1;
            }
        }
        printf("%d\n",i<=t?-1:cnt);
    }
    return 0;
}