시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 735 172 125 26.539%

문제

재홍이는 열심히 공부를 하고 있다가 머리를 식히려고 심심풀이로 문제를 풀어보기로 결심했다. 지금부터 그 심심풀이 문제를 설명하기로 하겠다.

1차원 좌표계상에 선분이 여러 개가 주어진다. 시작점과 선분이 끝나는 점이 재홍이에게 주어졌다. 재홍이는 이 많은 선분들이 최대로 겹쳐있는 부분의 겹친 선분의 개수가 알고 싶어졌다. 그런데 재홍이는 이미 공부를 너무 열심히 한 상태라 더 이상 프로그래밍을 할 여력이 없다. 재홍이를 도와 주어라. ㅋㅋㅋ

선분이 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.

입력

첫째줄에는 선분의 개수(N<=1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작좌표와 끝나는 좌표가 입력으로 들어온다.

출력

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

예제 입력

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

예제 출력

3

힌트

출처

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