백준 온라인 저지, 그리디 / 6068번: 시간관리하기 (파이썬 / 백준 골드문제)

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다. 

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입력

첫 줄에는 일의 개수인 N을 받고

두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

출력

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

제한

예제 입력 1

4
3 5
8 14
5 20
1 16

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjYwNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjMDQgXHVhZDAwXHViOWFjXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzFcdWMyZTRcdWQ1NWMgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YWQwMFx1YjlhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzc4IFx1YWU2OFx1YjJlY1x1YzU1OFx1YjJlNC4gXHVhZGY4XHViMjk0IE5cdWFjMWNcdWM3NTggXHVkNTc0XHVjNTdjXHVkNTYwIFx1Yzc3Y1x1YzVkMCZuYnNwOygxJmx0Oz1OJmx0Oz0xMDAwKSBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWU0XHVhY2JjXHViMmU0LiZuYnNwOyhcdWM2YjBcdWM3MjBcdWI5N2MgXHVjOWRjXHVhY2UwLCBcdWI5YzhcdWFkN2ZcdWFjMDRcdWM3NDQgXHVjZTU4XHVjNmIwXHVhY2UwLCBcdWIyZjRcdWM3YTVcdWM3NDQgXHVhY2UwXHVjZTU4XHViMjk0IFx1YjRmMVx1Yzc1OCk8XC9wPlxyXG5cclxuPHA+XHVjODc0XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZDAwXHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVhZGY4XHViMjk0IFx1YjA1ZFx1YjBiNFx1YzU3Y1x1YjljYyBcdWQ1NThcdWIyOTQgXHVjNzdjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YzY0NFx1YzEzMVx1YjQyMCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc0NCBUX2koMSZsdDs9VF9pJmx0Oz0xLDAwMCkgXHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3MCwgXHViMDVkXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBTX2koMSZsdDs9U19pJmx0Oz0xLDAwMCwwMDApIFx1Yzc3NFx1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHVkNTU4XHViOGU4XHVjNzU4IFx1YzJkY1x1Yzc5MVx1Yzc0NCB0ID0gMFx1YzczY1x1Yjg1YyBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3N2MgXHVkNTYwIFx1YjU0Y1x1YjI5NCBcdWFkZjgmbmJzcDtcdWM3N2NcdWM3NDQgXHViOWM4XHVjZTYwJm5ic3A7XHViNTRjIFx1YWU0Y1x1YzljMCBcdWFkZjggXHVjNzdjXHViOWNjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjODc0XHVjNzQwIFx1YjJhNlx1YzdhMCBcdWM3OTBcdWIyOTQgXHVhYzc4IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjJm5ic3A7XHVjODFjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWM4YyZuYnNwO1x1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU1Y1x1YjNjNFx1YzVkMFx1YzExYyZuYnNwO1x1Yzg3NFx1Yzc3NCZuYnNwO1x1YWMwMFx1YzdhNSBcdWIyYTZcdWFjOGMgXHVjNzdjXHVjNWI0XHViMDk4XHViM2M0IFx1YjQxOFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc4IE5cdWM3NDQgXHViYzFiXHVhY2UwPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4rMVx1YzkwNFx1YWU0Y1x1YzljMCBUX2lcdWM2NDAgU19pXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YjI5NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzRcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1IFx1ZDU1OFx1Yjc3Yy4gXHVjODc0XHVjNzc0IFx1YzgxY1x1YzJkY1x1YWMwNFx1YzVkMCBcdWM3N2NcdWM3NDQgXHViMDVkXHViMGJjIFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgLTEgXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2MDY4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGltZSBNYW5hZ2VtZW50IiwiZGVzY3JpcHRpb24iOiI8cD5FdmVyIHRoZSBtYXR1cmluZyBidXNpbmVzc21hbiwgRmFybWVyIEpvaG4gcmVhbGl6ZXMgdGhhdCBoZSBtdXN0IG1hbmFnZSBoaXMgdGltZSBlZmZlY3RpdmVseS4gSGUgaGFzIE4gam9icyBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwKSB0byBhY2NvbXBsaXNoIChsaWtlIG1pbGtpbmcgdGhlIGNvd3MsIGNsZWFuaW5nIHRoZSBiYXJuLCBtZW5kaW5nIHRoZSBmZW5jZXMsIGFuZCBzbyBvbikuPFwvcD5cclxuXHJcbjxwPlRvIG1hbmFnZSBoaXMgdGltZSBlZmZlY3RpdmVseSwgaGUgaGFzIGNyZWF0ZWQgYSBsaXN0IG9mIHRoZSBqb2JzIHRoYXQgbXVzdCBiZSBmaW5pc2hlZC4gSm9iIGkgcmVxdWlyZXMgYSBjZXJ0YWluIGFtb3VudCBvZiB0aW1lIFRfaSAoMSAmbHQ7PSBUX2kgJmx0Oz0gMSwwMDApIHRvIGNvbXBsZXRlIGFuZCBmdXJ0aGVybW9yZSBtdXN0IGJlIGZpbmlzaGVkIGJ5IHRpbWUgU19pICgxICZsdDs9IFNfaSAmbHQ7PSAxLDAwMCwwMDApLiBGYXJtZXIgSm9obiBzdGFydHMgaGlzIGRheSBhdCB0aW1lIHQ9MCBhbmQgY2FuIG9ubHkgd29yayBvbiBvbmUgam9iIGF0IGEgdGltZSB1bnRpbCBpdCBpcyBmaW5pc2hlZC48XC9wPlxyXG5cclxuPHA+RXZlbiBhIG1hdHVyaW5nIGJ1c2luZXNzbWFuIGxpa2VzIHRvIHNsZWVwIGxhdGU7IGhlbHAgRmFybWVyIEpvaG4gZGV0ZXJtaW5lIHRoZSBsYXRlc3QgaGUgY2FuIHN0YXJ0IHdvcmtpbmcgYW5kIHN0aWxsIGZpbmlzaCBhbGwgdGhlIGpvYnMgb24gdGltZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogVF9pIGFuZCBTX2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIGxhdGVzdCB0aW1lIEZhcm1lciBKb2huIGNhbiBzdGFydCB3b3JraW5nIG9yIC0xIGlmIEZhcm1lciBKb2huIGNhbm5vdCBmaW5pc2ggYWxsIHRoZSBqb2JzIG9uIHRpbWUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZhcm1lciBKb2huIGhhcyA0IGpvYnMgdG8gZG8sIHdoaWNoIHRha2UgMywgOCwgNSwgYW5kIDEgdW5pdHMgb2YgdGltZSwgcmVzcGVjdGl2ZWx5LCBhbmQgbXVzdCBiZSBjb21wbGV0ZWQgYnkgdGltZSA1LCAxNCwgMjAsIGFuZCAxNiwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiBtdXN0IHN0YXJ0IHRoZSBmaXJzdCBqb2IgYXQgdGltZSAyLiBUaGVuIGhlIGNhbiBkbyB0aGUgc2Vjb25kLCBmb3VydGgsIGFuZCB0aGlyZCBqb2JzIGluIHRoYXQgb3JkZXIgdG8gZmluaXNoIG9uIHRpbWUuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

접근 방법

- 주어진 일을 끝내야하는 시간을 기준으로 내림차순 정렬한다.
- 이후 일을 하나씩 탐색해나가며 여유 시간을 갱신해나간다.
- 여유 시간은 다음과 같이 갱신한다.
- min(현재까지의 여유시간, 끝내야하는 마감시간) - 현재 탐색 중인 일을 하는데 필요한 시간

코드

# https://www.acmicpc.net/problem/6068
# 접근 방법
# 주어진 일을 끝내야하는 시간을 기준으로 내림차순 정렬한다.
# 이후 일을 하나씩 탐색해나가며 여유 시간을 갱신해나간다.
# 여유 시간은 다음과 같이 갱신한다.
# min(현재까지의 여유시간, 끝내야하는 마감시간) - 현재 탐색 중인 일을 하는데 필요한 시간

n = int(input())
work = [list(map(int, input().split())) for _ in range(n)]
work.sort(key=lambda x:x[1], reverse = True)
spare_time = work[0][1]
for x in work:
    spare_time = min(x[1], spare_time) - x[0]
if spare_time >= 0:
    print(spare_time)
else:
    print(-1)