10045 회의실 배정 Silver II

문제

한 개의 회의실에서 N개의 회의를 진행하려고 한다. 각 회의의 시작 시간과 끝나는 시간이 주어질 때, 겹치지 않게 최대한 많은 회의를 배정하는 프로그램을 작성하시오.

입력

첫째 줄에 회의의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 회의의 시작 시간과 끝나는 시간이 주어진다. (0 ≤ 시작 < 끝 ≤ 1,000,000)

출력

최대 회의 수를 출력한다.

5
1 4
3 5
0 6
5 7
3 8

3