시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 401 | 197 | 146 | 48.026% |
수직선상에 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