usa_selfish/권영기

#include<iostream>
#include<algorithm>
using namespace std;
struct cow{
    int s1, s2;
};
cow c[50020], rc[50020];
int cc(cow a, cow b){
    if(a.s1 == b.s1)return a.s2<b.s2;
    return a.s1<b.s1;
}
int d[50020], check[50020];
int main(void){
 
    int n, m = 0;
    int i;
 
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d %d", &c[i].s1, &c[i].s2);
    }
    sort(c, c+n, cc);
    rc[m++] = c[0];
    for(i=1; i<n; i++){
        if(c[i].s1 != rc[m-1].s1){
            rc[m++] = c[i];
        }
    }
 
    for(i=0; i<=50000; i++)check[i] = 100000020;
    d[0] = 1;
    check[1] = rc[0].s2;
    for(i = 1; i<m; i++){
        if(check[d[i-1]] <= rc[i].s1)d[i] = d[i-1]+1;
        else d[i] = d[i-1];
 
        if(check[d[i]] > rc[i].s2)check[d[i]] = rc[i].s2;
    }
    printf("%d",d[m-1]);
}