알고리즘/수학

[백준]1263 시간관리 #그리디

씩씩한 IT블로그 2020. 6. 14. 14:55
반응형

1. 풀이

(1) 늦게 끝낼 수 있는 일부터 탐색하여 최대한 늦게 시작한다.

(2) (1)에서 탐색한 일이전의 일의 데드라인에 영향을 주면, 이전의 일영향받는만큼 늦게 시작한다.

 

2. 소스코드

N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int,input().split())))

def returnSecond(L):
    return L[1]

L.sort(key=returnSecond)

preStart=L[N-1][1]-L[N-1][0]
for i in range(N-2,-1,-1):
    if preStart<L[i][1]:
        preStart=preStart-L[i][0]
    else:
        preStart=L[i][1]-L[i][0]

if preStart<0:
    print(-1)
else:
    print(preStart)
반응형