시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 135 50 33 39.759%

문제

수직선상에 N(1 <= N <=25,000)개의 구간이 있다. 구간의 양 끝점은 각각 정수 좌표 한 개로 나타내어진다. 구간은 겹칠 수 있고, 어떤 구간이 다른 구간을 완전히 포함할 수도 있지만, 모든 구간은 다른 구간과 서로 자신의 끝점을 공유하지 않는다. (하나의 위치는 최대 하나의 구간의 어떤 끝점만이 될 수 있다.) 어떤 한 구간이 다른 구간들을 최대한 많이 포함하고 있는 개수를 찾으시오.

      *-----------*
      |           |
*-----------*
|           |
| *-*   *-* |
| | |   | | |
1 2 3 4 5 6 7 8 9 10

구간들의 배치가 위와 같은 경우, 답은 1-7구간이 포함하고 있는 다른 구간의 개수 2(2-3구간, 5-6구간)이다.

입력

첫째 줄에 N이 들어온다.
둘째 줄부터 N+1번째 줄까지 N개의 줄마다 각각 해당 구간을 나타내는 두 정수 A, B가 들어온다. (1 <= A < B <= 2,000,000,000)

출력

어떤 한 구간이 다른 구간들을 최대한 많이 포함하고 있는 개수를 출력하시오.

예제 입력

4
1 7
2 3
5 6
4 10

예제 출력

2

힌트