인쇄 회로 기판

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

요약

각 도선이 아래쪽 점과 위쪽 점을 잇는 N개의 도선이 주어질 때 서로 교차하는 도선끼리 같은 층에 둘 수 없다는 조건에서 필요한 최소 레이어 수를 구해야 하며, 이는 서로 교차하는 도선들의 최대 묶음 크기를 구하는 문제로 귀결됩니다.

난이도: 보통10점 중 5점
유형: 정렬, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

인쇄 회로 기판에서는 전기가 통하지 않는 판 위에 전도성 배선을 놓는다. 같은 층에 있는 두 도선은 서로 교차하면 합선이 생기므로, 복잡한 경우에는 전도성 판을 여러 층으로 나누고 각 층 사이를 전기가 통하지 않는 재료로 분리한 기판을 사용한다. 그러나 층이 많은 기판일수록 비용이 크기 때문에, 제조사는 필요한 도선들을 가능한 한 적은 수의 층에 배치하려고 한다.

이 문제에서는 모든 도선이 기판의 서로 마주 보는 두 변에 있는 단자를 잇는 기판을 다루며, 필요한 층의 수를 최소로 만드는 것이 목표이다.

아래 그림의 왼쪽에 있는 기판을 생각해 보자. 한 도선이 A와 B를 잇고 다른 도선이 D와 C를 이어야 한다면, 가운데 그림처럼 두 도선을 한 층에 놓을 수 있다. 그러나 A와 C를 잇는 도선과 D와 B를 잇는 도선은 오른쪽 그림처럼 같은 층에 놓을 수 없다.

$W \times H$ 크기의 기판 위에 놓인 $N$ 개의 도선의 양 끝점 위치가 주어질 때, 모든 도선을 수용하는 데 필요한 최소 층의 수를 구하는 프로그램을 작성하라.

도선의 폭은 단자 사이의 거리에 비해 매우 작다고 가정한다. 즉, 어떤 두 도선 사이에도 항상 세 번째 도선이 지날 공간이 충분히 있다.

입력

첫째 줄에 도선의 수 $N$ ( $1 \le N \le 10^5$ )이 주어진다. 이어지는 $N$ 개의 줄에는 각각 두 정수 $X_{i1}$ 과 $X_{i2}$ ( $0 \le X_{ij} \le 10^6$ )가 공백으로 구분되어 주어지며, 이는 $i$ 번째 도선이 점 $(X_{i1}, 0)$ 과 $(X_{i2}, H)$ 를 이어야 함을 뜻한다. 입력으로 주어지는 $2N$ 개의 끝점은 모두 서로 다르다고 가정한다.

출력

필요한 모든 도선을 수용하는 데 필요한 최소 층의 수를 정수 하나로 출력한다.

예제4

예제 1
입력
```
2
1 1
3 3
```
예상 출력
```
1
```
예제 2
입력
```
2
1 3
3 1
```
예상 출력
```
2
```
예제 3
입력
```
1
5 10
```
예상 출력
```
1
```
예제 4
입력
```
5
1 2
2 4
3 6
4 8
5 10
```
예상 출력
```
1
```