품평회 행사 > 문제은행



알고리즘 그리디

1831 : 품평회 행사

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 99 회    시도횟수: 207 회   



농부 철수는 품평회가 열리는 곳으로 돌아왔고, 그래서 특별한 행사들(콘서트, 로데오, 요리 쇼 등)에 참가할 수 있게 되었다. 

철수는 N(1 ≤ N ≤ 10,000) 가지 특별 행사들 중 그가 참가 할 수 있는 한 최대한 많은 행사에 참가하고 싶다.

 

철수는 ET의 자전거를 빌렸기 때문에, 한 행사에서 다음 행사로 갈 때 전혀 시간을 필요로 하지 않게 되었다(이동할 때 시간이 0이 필요하다!)

 

철수가 가고 싶은 행사들의 목록이 주어지고, 

행사의 시작 시간 (1 ≤ T ≤ 100,000)과 행사 진행 시간(1 ≤ L ≤ 100,000)이 주어졌을 때, 

철수가 참가할 수 있는 최대의 행사 수를 구하시오. 

철수는 절대로 행사가 끝나기 전에 떠나지 않는다.




1번째 줄: 한 개의 정수, N. 2번째 ~ N+1번째 줄: 각 줄은 공백으로 구분된 두 개의 정수 T와 L을 포함한다.




철수가 참가할 수 있는 행사 수의 최대값을 출력한다.



7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
4


입력데이터의 스케쥴을 그림으로 표현하면 다음과 같다.

철수는 행사 1, 2, 3, 4에 참가하는 것 보다 더 많은 행사에 참가할 수 없다.



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.