자전거 한 대의 하루

문제

공유 자전거 보관소는 정비가 끝난 자전거 한 대를 하루 동안 예약제로 운영한다. 운영자는 미리 접수된 예약 요청 가운데 일부를 골라 승인하려 한다. 각 요청에는 이용을 시작할 시각과 자전거를 반납할 시각이 정수로 적혀 있다. 승인된 요청은 적힌 시작 시각부터 반납 시각 직전까지 자전거 한 대를 독점한다. 모든 요청은 같은 날의 같은 자전거를 대상으로 하며, 다른 자전거를 가져오거나 요청에 적힌 시각을 바꾸는 일은 허용되지 않는다. 어떤 요청의 반납 시각이 다른 요청의 시작 시각과 같다면 두 요청을 모두 승인할 수 있다. 반납과 다음 대여 사이에 별도의 정비 시간은 필요하지 않다. 반대로 두 요청의 이용 시간이 조금이라도 겹치면 둘 중 하나만 승인할 수 있다. 이용 도중에 자전거를 나누어 사용하거나, 한 요청의 일부 시간만 승인하는 것은 불가능하다. 각 요청은 전부 승인하거나 전부 거절해야 한다. 운영자는 이용 시간의 총합이나 대여 요금보다 승인한 요청의 개수를 중요하게 생각한다. 따라서 서로 충돌하지 않는 요청을 골랐을 때 승인할 수 있는 요청 수의 최댓값을 구하려 한다. 오래 이용하는 요청과 짧게 이용하는 요청도 승인 개수를 셀 때는 각각 한 건으로 계산한다. 요청이 입력되는 순서는 접수 순서일 뿐이며 승인 순서를 제한하지 않는다. 서로 다른 요청의 시작 시각과 반납 시각이 모두 같을 수도 있다. 이 경우에도 각 요청은 별개의 요청이지만, 이용 시간이 겹치므로 동시에 승인할 수는 없다. 최대 개수를 만드는 선택이 여러 가지라면 어느 선택을 사용해도 된다. 출력에는 선택한 요청의 번호나 순서를 적지 않고, 최대 개수만 적는다. 접수된 요청이 하나도 없다면 승인할 수 있는 개수는 0이다.

입력

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

출력

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

6
0 4
1 2
2 5
4 6
5 7
7 8

4

4
3 9
3 9
3 9
3 9

1

0

0

출처: Devin.KR 자체 제작