천문대의 관측 신청표

문제

한 천문대는 밤 동안 관측 장비 한 대를 여러 신청자에게 나누어 사용하게 한다. 장비를 사용하려는 신청은 모두 N개이며, 각 신청에는 관측을 시작할 시각과 끝낼 시각이 정수로 적혀 있다. 시각은 그날의 운영 시작점을 기준으로 센 값이다. 천문대는 신청에 적힌 시간을 앞당기거나 늦출 수 없으며, 신청 하나를 받아들이면 그 신청의 관측 구간 전체를 배정해야 한다. 시작 시각이 S이고 종료 시각이 E인 신청은 S 이상 E 미만인 동안 장비를 사용한다. 따라서 한 신청의 종료 시각과 다른 신청의 시작 시각이 같으면 두 신청을 모두 받아들일 수 있다. 장비를 바꾸어 설치하거나 다음 관측을 준비하는 데에는 별도의 시간이 들지 않는다. 반면 두 신청이 양의 길이를 가진 시간 구간에서 겹치면, 두 신청을 동시에 받아들일 수 없다. 모든 신청은 S<E를 만족하므로 관측 시간이 0인 신청은 없다. 신청자들은 관측 대상과 관계없이 같은 장비를 사용한다. 어떤 신청을 먼저 받았는지, 신청자의 이름이 무엇인지, 관측 시간이 얼마나 긴지는 선정 기준이 아니다. 천문대가 원하는 것은 서로 충돌하지 않는 신청을 골라 받아들이는 신청의 개수를 최대화하는 것이다. 신청 일부만 수행하거나 하나의 신청을 여러 조각으로 나누어 배정하는 일은 허용하지 않는다. 입력에 같은 시작 시각과 종료 시각을 가진 신청이 여러 번 등장할 수도 있다. 이들은 각각 별개의 신청이지만 같은 시간에 장비를 사용해야 하므로 그중 둘을 함께 받아들일 수는 없다. 신청이 입력된 순서는 실제 관측 순서와 무관하다. 최대 개수를 만드는 선택이 여러 가지여도 어느 신청을 골랐는지는 출력하지 않는다. 받아들일 수 있는 신청 개수의 최댓값만 출력한다. 신청이 하나도 들어오지 않은 경우에는 그 값이 0이다.

입력

첫째 줄에 정수 N이 주어진다.
다음 N개 줄에는 각 신청의 시작 시각 S와 종료 시각 E가 공백으로 구분되어 주어진다.
0≤N≤20,000이며, 모든 시각은 정수이고 0≤S<E≤99,999다.

출력

서로 충돌하지 않게 받아들일 수 있는 신청 개수의 최댓값을 정수 하나로 출력한다. N=0이면 0을 출력한다.

6
0 5
1 3
3 6
5 8
6 9
9 11

4

4
2 7
2 7
3 6
4 5

1

0

0

출처: Devin.KR 자체 제작