이번 문제는 그리디 알고리즘을 통해 해결하였다. 가장 빨리 끝내는 시간과 가능 여부를 물어봤다면 종료 시간에 대한 오름차순으로 정렬을 했을 것이다. 그러나 여유롭게 시작하는 시간을 물어봤기 때문에 works 리스트를 종료 시간에 대한 내림차순으로 정렬을 하였다. 그리고 가장 여유롭게 끝낼 수 있는 시간인 works[0]의 종료 시간을 현재 시간으로 설정하였고, works를 순회하며 현재 시간에서 현재 work의 소요 시간을 빼주었다. 이때 현재 시간이 work의 종료시간보다 클 경우에는 마감 시간을 지키지 못한 것이므로 현재 시간을 work의 종료시간과 같도록 갱신해주었고, 현재 시간이 work의 소요시간보다 작을 경우에는 작업을 수행할 수 없는 경우이므로 -1을 출력하고 프로그램을 종료하도록 하였다. 이 과정을 모두 거친 후의 현재 시간이 일을 여유롭게 시작할 수 있는 시간이다.

Code

n = int(input())
works = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[1], reverse=True)
cur = works[0][1]
for i in range(n):
    if cur > works[i][1]:
        cur = works[i][1]
    if cur < works[i][0]:
        print(-1)
        quit()
    cur -= works[i][0]
print(cur)