보조 창구의 예약표

문제

은행은 서류 확인 업무가 몰리는 날에 보조 창구 하나를 운영한다. 이 창구를 이용하려는 고객들은 각자 업무를 시작할 시각과 마칠 시각을 정해 예약 요청을 제출했다. 고객의 다른 일정과 연결된 요청이므로 은행은 요청에 적힌 시각을 앞당기거나 늦출 수 없다. 요청을 승인하면 그 고객의 업무를 정해진 구간 전체에 걸쳐 처리해야 한다. 각 요청에는 시작 시각 S와 종료 시각 E가 적혀 있다. 두 시각은 같은 기준 시점부터 지난 분을 나타내는 정수이며 S는 E보다 작다. 승인된 요청은 S 시각에 창구 사용을 시작하고 E 시각에 사용을 마친다. 한 고객이 창구를 사용하는 동안 다른 고객의 업무를 동시에 처리할 수 없다. 다만 업무가 끝난 즉시 다음 업무를 시작할 수 있으므로, 앞 요청의 종료 시각과 다음 요청의 시작 시각이 같아도 두 요청을 모두 승인할 수 있다. 은행은 제출된 요청 중 일부를 승인하여 보조 창구에서 처리하는 요청의 수를 최대화하려 한다. 고객마다 업무의 중요도나 보상에 차이는 없으며, 업무 시간이 길어도 처리한 요청 한 건으로 센다. 요청을 나누어 처리하거나 중간에 멈췄다가 이어서 처리하는 것은 허용되지 않는다. 시작 시각과 종료 시각이 모두 같은 요청이 여러 개 들어와도 각각 별개의 요청이지만, 사용 시간이 겹치면 함께 승인할 수 없다. 승인한 요청 사이에 창구를 사용하지 않는 시간이 있어도 괜찮다. 모든 요청을 승인할 필요도 없으며, 승인하지 않은 요청은 다른 창구로 안내된다. 요청 목록이 제출된 순서는 실제 처리 순서와 관계가 없다. 주어진 예약 요청에서 서로 충돌하지 않게 승인할 수 있는 최대 요청 수를 구해야 한다. 최대 개수를 만드는 승인 목록이 여러 개라면 어느 목록을 선택해도 되며, 목록 자체는 출력하지 않는다.

입력

첫째 줄에 예약 요청 수 N이 주어진다. N은 1 이상 20,000 이하의 정수다.
다음 N개 줄에는 각 요청의 시작 시각 S와 종료 시각 E가 공백으로 구분되어 주어진다. S와 E는 0 이상 1,000,000 이하의 정수이며, 항상 S < E다.
같은 시작 시각이나 종료 시각을 가진 요청과 완전히 동일한 요청이 여러 번 주어질 수 있다.

출력

한 보조 창구에서 시간이 겹치지 않게 승인할 수 있는 최대 요청 수를 정수 하나로 출력한다. 종료 시각과 다음 시작 시각이 같은 요청들은 함께 승인할 수 있다.

6
0 4
1 3
3 5
4 7
5 6
6 8

4

3
2 5
2 5
2 5

1

4
0 1
1 2
2 3
3 4

4

출처: Devin.KR 자체 제작