Informatica Online Judge

  컨퍼런스 홀 [1405 / 057D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 21   Total Tried : 159


The Champion of this Problem (C++) : gs19022 - 0ms / 307byte
My Best Submission (C++) : N/A

[]

Background

경기과학고 컨퍼런스홀은 교육청 및 근처 학교 행사를 위해 거의 매일 대여를 해주고 있다.

행정실 담당자는 매일매일 들어오는 행사요청 때문에 다른 업무가 마비되어 2016년부터는 행사를 요청하는 기관을 미리 받아 행사가 가능한 기관을 정하기로 하였다.

담당자는 하나밖에 없는 컨퍼런스홀을 여러기관이 하루에 동시에 사용하지 않으면서 최대한 많이 사용될 수 있도록 스케줄을 짜는 프로그램을 작성하고 싶다.

예를들어, 다음과 같은 일정 요청이 들어오면 담당자는 경기도교육청, 수일여중, 조원고만 대여 가능 응답을 해 줄 수 있다.

1) 경기도교육청 2일부터 5일간 (2,3,4,5,6,7)
2) 수원교육지원청 9일부터 7일간
3) 수일여중 15일 부터 6일간
4) 조원고 9일부터 3일간

만약 수원교육지원청을 대여해주면 수일여중과 조원고가 사용할 수 없어 수원교육지원청은 대여 거부를 해야 한다.

Input

첫번째 줄에 행사의 개수 N이 주어진다. N은 100,000 이하의 자연수이다.

이후 N개의 줄에 행사 시작 날짜 S와 기간 D가 주어진다. 이는 [S, S + D] 일 동안 대여를 해준다는 뜻이다. S와 S+D는 32비트 정수 범위 내이다.

Output

행사가 가능한 기관의 최대수를 출력한다.

IO Example

입력
4
2 5
9 7
15 6
9 3

출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]