가장 많이 포함하는 구간
시간 제한2초메모리 제한128 MB
끝점이 모두 다른 N개의 구간이 주어질 때, 한 구간에 완전히 포함되는 다른 구간의 최대 개수를 구합니다.
문제
수직선 위에 N개의 구간이 있다. 각 구간의 양 끝점은 하나의 정수 좌표로 표현된다. 구간들은 서로 겹칠 수 있고, 어떤 구간이 다른 구간을 완전히 포함할 수도 있다. 단, 어떤 두 구간도 끝점을 공유하지 않는다. 즉, 같은 좌표가 둘 이상의 구간 끝점으로 쓰이는 일은 없다.
구간 [a, b]가 구간 [c, d]를 포함한다는 것은 a < c이고 d < b임을 뜻한다. 한 구간이 포함할 수 있는 다른 구간의 개수 중 최댓값을 구하라.
*-----------*
| |
*-----------*
| |
| *-* *-* |
| | | | | |
1 2 3 4 5 6 7 8 9 10
위 그림과 같은 배치에서는 1-7 구간이 2-3 구간과 5-6 구간을 포함하므로 답은 2이다.
입력
첫째 줄에 구간의 개수 N이 주어진다. (1 <= N <= 25,000)
둘째 줄부터 N개의 줄에 걸쳐 각 구간을 나타내는 두 정수 A, B가 주어진다. (1 <= A < B <= 2,000,000,000)
출력
한 구간이 포함할 수 있는 다른 구간의 최대 개수를 출력한다.