반납 수레 점검일

문제

한 도서관에서는 반납된 책을 수레에 모아 두었다가 정해진 기간 안에 한 번씩 점검한다. 수레마다 책이 모두 모이는 날과 다음 운반을 위해 수레를 비워야 하는 날이 다르므로, 점검할 수 있는 날짜도 서로 다르다. 담당자는 출근하여 점검하는 날짜의 수를 최대한 줄이려고 한다. 수레는 모두 N개이며, 1번부터 N번까지 번호가 붙어 있다. i번 수레에는 두 정수 L_i와 R_i가 적혀 있다. 이 수레는 L_i일 이상 R_i일 이하인 정수 날짜에 점검해야 한다. 양 끝 날짜에도 점검할 수 있으며, 해당 기간 중 한 번만 점검하면 된다. 다른 수레와 같은 날짜에 점검해도 된다. 담당자가 어떤 날짜를 점검일로 정하면 그날 점검할 수 있는 수레를 원하는 만큼 점검할 수 있다. 수레 하나를 점검하는 데 걸리는 시간은 별도로 고려하지 않으며, 하루에 처리할 수 있는 수레 수에도 제한이 없다. 따라서 여러 수레의 점검 가능 기간에 공통으로 들어가는 날짜가 있다면, 그 수레들을 모두 같은 날 처리할 수 있다. 모든 수레를 점검할 수 있도록 점검일들을 정할 때, 선택해야 하는 서로 다른 날짜의 최소 개수를 구한다. 같은 날짜를 여러 번 선택해도 하루로만 센다. 수레를 점검하는 순서와 실제로 선택한 날짜들은 출력하지 않는다. 모든 수레의 점검 가능 기간은 비어 있지 않으므로, 조건을 만족하는 일정은 항상 존재한다. 최적 일정이 여러 개여도 필요한 날짜의 개수만 같으면 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개 줄의 i번째 줄에 정수 L_i와 R_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 30,000
1 ≤ L_i ≤ R_i ≤ 100,000
입력에 등장하는 모든 수는 정수다.

출력

모든 수레를 점검하기 위해 필요한 서로 다른 점검일의 최소 개수를 한 줄에 출력한다.

5
2 5
4 7
5 5
8 10
9 12

2

4
1 1
2 2
3 3
4 4

4

출처: Devin.KR 자체 제작