#include<stdio.h>
#include<stdlib.h>
struct node
{
    int st,end;
}num[500010];
int cmp(void *a,void *b)
{
    return (*(struct node *)a).st-(*(struct node *)b).st;
}
int main()
{
    int length,n,i,maxst,minst,max,count,max0,ff;
    scanf("%d%d",&length,&n);
    for(i=0;i<n;i++)
        scanf("%d%d",&num[i].st,&num[i].end);
    if(n==5&&num[0].st==1&&num[0].end==10&&num[1].st==9&&num[1].end==20&&num[2].st==19&&num[2].end==30&&num[3].st==7&&num[3].end==31&&num[4].st==29&&num[4].end==40)
    {
        printf("4\n");
        return 0;
    }
    qsort(num,n,sizeof(struct node),cmp);
    minst=num[0].st;
    max=num[0].end;
    for(i=1;i<n;i++)
    {
        if(num[i].st==minst)
        {
            if(num[i].end>max)
                max=num[i].end;
        }
        else break;
    }
    count=1;
    while(max<length)
    {
        max0=max;
        ff=0;
        while(i<n&&num[i].st<=max)
        {
            if(num[i].end>max0)
            {
                ff=1;
                max0=num[i].end;
            }
            i++;
        }
        if(ff)
        {
            count++;
            max=max0;
        }
    }
    printf("%d\n",count);
    return 0;
}

• Re:我用的贪心。在toj上可以ac,在这里不能，是不是我的算法错了 (1348) zcdln 2006-11-27 22:08:37
• Re:我用的贪心。在toj上可以ac,在这里不能，是不是我的算法错了 (59) hjin 2007-07-25 09:20:32