#include<iostream>
using namespace std;

typedef struct{
    int x;
    int y;
}node;

node nodes[50002];
//int use[50002];

int cmp(const void *pl, const void *pr){
    node *p1 = (node*)pl; 
    node *p2 = (node*)pr;
    if(p1->x == p2->x)
        return p1->y - p2->y;
    return p1->x - p2->x;
}

int main(){
    int num;
    while(cin>>num && num){
        for(int i=0;i<num;i++)
            cin>>nodes[i].x>>nodes[i].y;
        qsort(nodes, num, sizeof(node), &cmp);
  //      memset(use, 0, num*sizeof(int));
        int total=1;
        int max=nodes[num-1].y;
        for(int i=num-2;i>=0;i--){
            if(max<nodes[i].y){
                max=nodes[i].y;
                total++;
            }
        }
        cout<<total<<endl;
    }
}

• scanf真是神武阿~ (863) zyz 2007-05-06 21:26:55
• 有个qsort呢。。还O(n)。。╭∩╮（︶︿︶）╭∩╮ (863) 225 2008-10-01 15:46:48
• Re:受不了了, O(n)的算法都超时 (872) qingjiquan 2011-07-29 11:30:51