시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB3028116389540.171%

문제

1차원 좌표계 위에 선분 N개가 있다. 선분이 최대로 겹쳐있는 부분의 겹친 선분의 개수를 구해보자. 선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.

입력

첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표 s와 끝나는 좌표 e (s < e)가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수이다.

출력

첫째 줄에는 최대로 많이 겹치는 선분들의 개수를 출력한다.

예제 입력 1

11
1 2
3 6
7 8
10 11
13 16
0 5
5 6
2 5
6 10
9 14
12 15

예제 출력 1

3

출처

  • 문제를 만든 사람: author9
  • 빠진 조건을 찾은 사람: koosaga