스마트 홈의 조용한 작업 시간

문제

한 스마트 홈에는 소리가 큰 자동 작업을 조정하는 관리 장치가 있다. 바닥 청소, 환기 통로 점검, 물탱크 세척 같은 작업을 동시에 실행하면 집 안의 소음이 커지므로, 관리 장치는 한 번에 하나의 작업만 실행하도록 설정되어 있다. 오늘 신청된 작업은 N개이며 각 작업에는 시작 시각과 종료 시각이 미리 정해져 있다. 관리 장치는 이 중 일부를 골라 실제로 실행한다. 작업 i의 시작 시각을 S_i, 종료 시각을 E_i라고 한다. 이 작업을 선택하면 S_i부터 E_i 직전까지 장치를 사용한다. 시작 시각을 미루거나 종료 시각을 앞당길 수 없으며, 실행 도중에 중단하거나 여러 구간으로 나눌 수도 없다. 작업 하나가 끝나는 바로 그 시각에 다른 작업을 시작하는 것은 가능하다. 예를 들어 종료 시각이 12인 작업과 시작 시각이 12인 작업은 함께 선택할 수 있다. 각 신청은 서로 별개의 작업이다. 두 신청의 시작 시각과 종료 시각이 모두 같더라도 하나의 신청으로 합치지 않는다. 다만 모든 작업의 실행 시간이 양수이므로, 시간이 완전히 같은 두 작업을 동시에 선택할 수는 없다. 작업의 종류나 실행 시간에 따른 가중치는 없으며, 작업 하나를 완료할 때마다 완료 개수가 정확히 1 증가한다. 장치를 사용하지 않고 비워 두는 시간에는 제한이나 추가 비용이 없다. 관리 장치의 목표는 선택한 작업들의 실행 시간이 서로 겹치지 않게 하면서 완료하는 작업의 개수를 최대화하는 것이다. 전체 실행 시간의 합을 최대화하거나 대기 시간을 최소화할 필요는 없다. 최대 개수를 만드는 선택 방법이 여러 가지라면 어느 방법을 택해도 되며, 선택한 작업의 번호나 실행 순서는 출력하지 않는다. 주어진 신청 내역으로 오늘 완료할 수 있는 작업 개수의 최댓값을 구한다.

입력

첫째 줄에 작업 수 N이 주어진다. 다음 N개의 줄 중 i번째 줄에 작업 i의 시작 시각 S_i와 종료 시각 E_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1 ≤ N ≤ 30,000, 0 ≤ S_i < E_i ≤ 9,999다. 작업은 임의의 순서로 주어진다.

출력

서로 시간이 겹치지 않게 선택할 수 있는 작업 개수의 최댓값을 정수 하나로 출력한다.

6
0 3
1 2
2 4
3 5
4 6
6 8

4

4
2 7
2 7
3 6
4 5

1

출처: Devin.KR 자체 제작