LinkNet

시간 제한1초메모리 제한128 MB

요약

직선 위 구간들로 주어진 전송들을, 같은 tick에서 어떤 구간도 다른 구간의 끝점을 내부에 포함하지 않고 각 점이 한 tick에 한 번만 쓰이도록 배치할 때 필요한 최소 tick 수를 구한다.

난이도: 보통10점 중 7점
유형: 구간, 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

LinkNet 네트워크에서 컴퓨터들은 하나의 통신 회선에 연결되어 있다. 연결할 수 있는 접속점들은 한쪽 끝에서부터 차례로 $0, 1, \ldots, R$ 번으로 번호가 매겨져 있다. 각 접속점에는 최대 한 대의 컴퓨터만 연결할 수 있으며, 각 컴퓨터는 정확히 하나의 접속점에만 연결된다. 회선의 통신은 동기식으로 이루어지며, 틱(tick) 이라고 부르는 이산적인 시간 단위마다 진행된다.

한 틱 동안 접속점 $a$ 와 $b$ ( $0 \le a < b \le R$ ) 에 연결된 두 컴퓨터가 데이터를 주고받으려면, $a < c < b$ 를 만족하는 어떤 중간 접속점 $c$ 에 연결된 컴퓨터도 그 틱 동안 어떤 전송에도 참여하지 않아야 한다. 또한 한 틱 동안 각 컴퓨터는 최대 한 번의 전송에만 참여할 수 있다.

수행해야 하는 전송들의 목록이 주어진다. 이 목록을 읽어, 모든 전송을 수행하는 데 충분한 최소 틱 수를 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 전송의 개수 $N$ ( $0 \le N \le 100000$ ) 이 주어진다. 이어지는 $N$ 개의 줄에는 각각 하나의 전송이 두 정수 $a$ , $b$ ( $0 \le a < b \le 10^9$ ) 로 주어지며, 두 수는 공백 하나로 구분된다. $a$ 와 $b$ 는 데이터를 전송할 두 접속점의 번호이다.

출력

모든 전송을 수행하는 데 충분한 최소 틱 수를 한 줄에 하나의 정수로 출력한다.

예제2

예제 1
입력
```
4
10 20
3 10
5 35
20 50
```
예상 출력
```
3
```
예제 2
입력
```
2
0 10
10 20
```
예상 출력
```
2
```