hdoj2037

今年暑假不AC

很增加人的自信的一道题

/***************************************************************\
 *Author: 小呼
 *Created Time: Sun 11 Jul 2010 07:40:53 PM CST
 *File Name: main.cpp
 *Description:贪心问题。
\***************************************************************/
//*========================*Head File*========================*\\

#include<iostream>
#include<stdlib.h>
/*----------------------*Global Variable*----------------------*/
int n;
typedef struct Event{//节目
    int s,e;//开始时间和结束时间
}Event;
Event E[1000];
//*=======================*Main Program*=======================*//
using namespace std;

int cmp(const void* a,const void* b){
    return ((Event*)a)->e-((Event*)b)->e;
}
int main(){
    while(cin>>n&&n){
        for(int i=0;i<n;++i)
          cin>>E[i].s>>E[i].e;
        qsort(E,n,sizeof(Event),cmp);//按结束时间排序
        int res=0;//问题结果
        int end=0;//上一个节目结束时间，初始化为0
        int p=0;//正在处理的节目的下标
        while(p<n){
            while(p<n&&E[p].s<end) p++;
            if(p<n){
                res++;
                end=E[p].e;
            }
        }
        cout<<res<<endl;
    }
}