=== 풀이 ===
{{{
import java.util.Arrays; 
import java.util.Comparator; 
import java.util.Scanner; 
  
class pair { 
    int a; 
    int b; 
      
    pair(int a, int b) { 
        this.a = a; 
        this.b = b; 
    } 
} 
  
public class Main{ 
    public static void main(String ar[]) {       
        Scanner scan = new Scanner(System.in); 
        int n = scan.nextInt(); 
          
        pair[] p = new pair[n]; 
          
        for(int i=0; i<n; i++) 
            p[i] = new pair(scan.nextInt()-1, scan.nextInt()-1); 
          
        Arrays.sort(p, new myCmp()); 
        int last = p[n-1].b; 
          
        int[] ans = new int[last+1]; 
          
        Arrays.fill(ans, 0, p[0].b, 0); 
          
        for(int i=0; i<n; i++) { 
            if(i != 0)  
                Arrays.fill(ans, p[i-1].b, p[i].b, ans[p[i-1].b]); 
                  
            ans[p[i].b] = Math.max(ans[p[i].a] +1, ans[p[i].b-1]);               
        } 
  
        System.out.println(ans[last]); 
                  
    } 
} 
  
class myCmp implements Comparator<pair> { 
    public int compare(pair o1, pair o2) { 
        if(o1.b < o2.b) return -1; 
        else if(o1.b == o2.b) { 
            if(o1.a < o2.a) return -1; 
            else if(o1.a == o2.a) return 0; 
            else return 1; 
        } 
        else return 1; 
    } 
}
}}}
----
[ACM_ICPC/2012스터디]