자전거 한 대의 예약표

문제

공유 자전거 보관소에서 시범 운영에 사용할 자전거 한 대를 따로 마련했다. 운영자는 이 자전거에 들어온 예약 요청을 검토하고 있다. 각 요청에는 대여를 시작할 시각과 반납할 시각이 정해져 있다. 요청을 승인하면 이용자는 정해진 시작 시각부터 자전거를 사용하고, 정해진 반납 시각에 같은 보관소로 돌아온다. 모든 이용자는 약속한 시각을 정확히 지킨다. 자전거는 한 대뿐이므로 사용 시간이 겹치는 두 요청을 함께 승인할 수 없다. 다만 반납과 다음 대여에 걸리는 시간은 없다고 본다. 따라서 어떤 요청의 반납 시각이 다른 요청의 시작 시각과 같다면 두 요청을 모두 승인할 수 있다. 예를 들어 시각 2에 시작해 시각 5에 반납하는 요청과 시각 5에 시작하는 요청은 서로 충돌하지 않는다. 요청 하나를 승인하려면 그 요청의 전체 사용 시간을 보장해야 한다. 시작이나 반납 시각을 바꾸거나, 사용 시간을 나누거나, 이용 도중에 다른 자전거로 바꾸는 일은 허용되지 않는다. 모든 요청은 승인했을 때 똑같이 한 건으로 센다. 이용 시간이 길거나 짧다는 이유로 별도의 점수를 주지 않는다. 입력에 같은 시작 시각과 반납 시각을 가진 요청이 여러 개 있더라도 각각 별개의 요청이며, 서로 시간이 겹치면 동시에 승인할 수 없다. 운영자는 서로 충돌하지 않도록 일부 요청을 골라 승인하려 한다. 승인할 수 있는 요청 수의 최댓값을 구하는 프로그램을 작성한다. 최댓값을 만드는 선택이 여러 가지여도 그중 하나를 구별할 필요는 없으며, 요청의 번호나 실제 예약표는 출력하지 않는다. 요청이 하나도 들어오지 않았다면 승인할 수 있는 요청 수도 0이다. 자전거는 첫 번째로 승인한 요청의 시작 시각 이전부터 보관소에 준비되어 있다.

입력

첫째 줄에 예약 요청 수 N이 주어진다. N은 0 이상 30,000 이하의 정수다.
다음 N개의 줄에 각 요청의 시작 시각 S와 반납 시각 E가 공백으로 구분되어 주어진다. S와 E는 정수이며 0 ≤ S < E ≤ 1,000,000,000이다.
요청은 임의의 순서로 주어진다.

출력

서로 사용 시간이 겹치지 않게 승인할 수 있는 요청 수의 최댓값을 정수 하나로 출력한다. 요청이 없으면 0을 출력한다.

6
0 4
1 2
2 5
4 6
5 7
7 9

4

4
3 8
3 8
4 7
5 6

1

0

0

출처: Devin.KR 자체 제작