POJ 2376

排序后贪心，有个小地方容易出错。

//384K    63MS

#include <iostream>
#include <stdio.h>
using namespace std;

typedef struct _node{
    int b,e;
}Node;

const int MN=25001;
Node In[MN];
bool Use[MN];
int N,T;
int ans=0;
bool wrong=false;

int cmp(const void* a,const void* b)
{
    Node* ap=(Node*)a;
    Node* bp=(Node*)b;
    if(ap->b!=bp->b)
        return ap->b-bp->b;
    else
        return bp->e-ap->e;
}

int main()
{
    scanf("%d%d",&N,&T);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&In[i].b,&In[i].e);

    qsort(&In[1],N,sizeof(Node),cmp);
    memset(Use,false,sizeof(Use));
    int front,end;
    front=In[1].b;
    if(front!=1){
        printf("-1\n");
        return 0;
    }
    end=In[1].e;
    Use[1]=true;
    ans++;
    int max,now;
    now=1;
    while(end<T&&ans<N){
        max=0;
        int flag=-1;
        for(int i=now+1;i<=N;i++){
            if(!Use[i]&&In[i].b<=end+1){//为end+1  容易错
                if(In[i].e>max)
                {
                    max=In[i].e;
                    flag=i;
                }
            }
            if(In[i].b>end+1)
                break;
        }
        if(flag!=-1){
            end=(max>end?max:end);
            ans++;
            Use[flag]=true;
            now=flag;
            if(end==T)
                break;
        }
        else if(end<T){
            wrong=true;
            break;
        }
    }
    if(!wrong&&end==T)
        printf("%d\n",ans);
    else
        printf("-1\n");
    return 0;
}