#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]); }
ACM_ICPC/2012스터디