한 대로 운영하는 임시 대여소

문제

강변 행사장에 임시 공유 자전거 대여소가 설치되었다. 이 대여소에는 사용할 수 있는 자전거가 한 대뿐이다. 운영자는 행사 전에 들어온 대여 신청을 확인하고, 서로 시간이 겹치지 않는 신청을 골라 승인하려고 한다. 모든 신청은 승인이 이루어지기 전에 이미 도착해 있으며, 신청이 입력된 순서는 승인 우선순위와 관계가 없다. 각 신청에는 대여 시작 시각과 반납 시각이 적혀 있다. 어떤 신청을 승인하면 해당 시작 시각부터 반납 시각 직전까지 자전거를 그 신청자에게 내주어야 한다. 시작 시각이나 반납 시각을 변경할 수 없으며, 신청의 일부 시간만 승인할 수도 없다. 자전거를 사용하고 있는 동안 다른 신청자에게 같은 자전거를 내줄 수 없다. 반납은 약속된 시각에 즉시 완료된다. 따라서 한 신청의 반납 시각이 다른 신청의 시작 시각과 같다면 두 신청을 모두 승인할 수 있다. 자전거를 점검하거나 다음 신청자에게 전달하는 데 추가로 걸리는 시간은 없다. 첫 신청이 시작하기 전에는 자전거가 대여소에 준비되어 있으며, 마지막 반납 시각에 대한 별도의 운영 종료 제한도 없다. 운영자의 목표는 승인한 신청의 개수를 가장 크게 만드는 것이다. 이용 시간의 총합이나 대여료는 고려하지 않는다. 입력에서 시작 시각과 반납 시각이 모두 같은 신청이 여러 번 등장하더라도 각각 서로 다른 신청이다. 다만 한 대의 자전거를 동시에 이용할 수 없다는 규칙은 이 경우에도 그대로 적용된다. 승인할 신청을 여러 가지 방법으로 고를 수 있다면 어느 방법을 선택해도 된다. 신청 번호나 선택한 순서를 출력할 필요는 없다. 주어진 모든 신청 중 규칙을 지키며 승인할 수 있는 신청 개수의 최댓값을 구한다.

입력

첫째 줄에 신청 수 N이 주어진다.
다음 N개 줄에 각 신청의 시작 시각 S와 반납 시각 E가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 30,000, 0 ≤ S < E ≤ 9,999이다.

출력

승인할 수 있는 신청 개수의 최댓값을 정수 하나로 출력한다.

6
0 4
1 3
3 5
4 7
5 6
6 9

4

4
2 8
2 8
3 7
4 6

1

1
0 1

1

출처: Devin.KR 자체 제작