빈 상영관의 점검 순서

문제

한 영화관은 정식 영업을 시작하기 전에 여러 상영관에서 시험 영상을 재생한다. 점검 담당자는 시험 영상 하나를 처음부터 끝까지 직접 보면서 화면과 소리가 맞는지 확인한다. 담당자는 한 명뿐이므로 시간이 겹치는 두 시험 영상을 모두 점검할 수는 없다. 영화관은 이미 시험 영상의 재생 시간을 확정했으며, 담당자의 선택에 따라 시간을 바꾸지는 않는다. 각 시험 영상에는 시작 시각 S와 종료 시각 E가 정수로 주어진다. 시각은 점검일의 기준 시점으로부터 지난 분을 뜻하며, 항상 S < E이다. 어떤 영상을 선택하면 시작 시각 S부터 종료 시각 E까지 그 영상의 점검을 맡는다. 도중에 점검을 멈추거나 늦게 들어간 영상은 완료한 영상으로 세지 않는다. 선택하지 않은 시험 영상은 그대로 재생되지만 담당자의 일정에는 영향을 주지 않는다. 담당자는 영상의 종료 시각에 즉시 다음 상영관으로 이동할 수 있다. 따라서 앞 영상의 종료 시각과 다음 영상의 시작 시각이 같아도 두 영상을 연속으로 점검할 수 있다. 이동이나 기록에 별도의 시간은 들지 않으며, 첫 번째로 선택한 영상의 시작 시각 이전에는 언제든 대기할 수 있다. 서로 다른 시험 영상의 시작 시각과 종료 시각이 모두 같을 수도 있으며, 이 경우에도 각 영상은 별개의 점검 대상이다. 영화관은 점검을 마친 영상의 개수만으로 작업량을 평가한다. 영상의 길이나 상영관 번호는 평가에 영향을 주지 않는다. 모든 영상을 점검할 필요는 없으며, 담당자는 시간 충돌이 없는 영상들을 골라 점검한다. 완료할 수 있는 시험 영상 개수의 최댓값을 구한다. 같은 최댓값을 만드는 선택이 여러 개여도 선택 목록은 출력하지 않는다. 시험 영상이 하나도 없으면 완료할 수 있는 개수는 0이다.

입력

첫째 줄에 시험 영상의 개수 N이 주어진다. N은 0 이상 20,000 이하의 정수이다.
다음 N개 줄에는 각 시험 영상의 시작 시각 S와 종료 시각 E가 공백으로 구분되어 주어진다. S와 E는 정수이며 0 ≤ S < E ≤ 1,440이다.
영상은 임의의 순서로 주어지며, 같은 시각 쌍이 여러 번 주어질 수 있다.

출력

완료할 수 있는 시험 영상 개수의 최댓값을 정수 하나로 출력한다. N이 0이면 0을 출력한다.

6
0 8
1 3
3 5
5 7
7 10
2 9

4

4
20 25
20 25
20 25
20 25

1

0

0

출처: Devin.KR 자체 제작