[python 백준 6068] 시간 관리하기

접근 방법

최소 이 시간까지는 일을 시작해야한다!

그러기 위해선 마감시간이 제일 늦은 시간을 기준으로 일하는 시간을 차례대로 뺌

 

제일 마지막 마감 시간을 기준으로 수행

[(3, 5), (8, 14), (5, 20), (1, 16)] 으로 설명하자면

1. 마감 시간을 기준으로 내림차순
   [(20, 5), (16, 1), (14, 8), (5, 3)]
2. 제일 늦은 마감 시간 가져온 후 일하는 시간 빼기
   null
   null
3. 그 다음 마감 시간 가져와서 비교
   null
4. 일하는 시간 빼기
   null
5. 그 다음 마감 시간 가져와서 비교
   null
6. 일하는 시간 빼기
   null
7. 그 다음 마감 시간 가져와서 비교
   null

여기서 남은 시간(6)보다 마감 시간(5)이 빠를 경우 제 시간에 못하기 때문에
마감 시간을 기준으로 일할 시간(3)을 빼야함

8. 일하는 시간 빼기
   

   

   null

즉, 적어도 2시부터 일을 해야 제시간에 마칠 수 있다.

 

정답 코드

우선 순위 큐 사용함

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

# 마감 시간 기준으로 최대힙
for i in range(n):
    t, e = map(int, sys.stdin.readline().split())
    heapq.heappush(heap, (-e, t))


last = heapq.heappop(heap)
last_time = abs(last[0] + last[1])
while heap:
    last = heapq.heappop(heap)
    if -last[0] >= last_time:
        last_time -= last[1]
    # 마감 시간보다 현재 남은 시간이 클 경우
    else:
        last_time = -last[0]
        last_time -= last[1]

# 제시간에 끝낼 수 없는 경우
if last_time < 0:
    print(-1)
else:
    print(last_time)

끝내야 하는 시간 기준으로 최대힙을 하기 위해 (e(마감시간), t(걸리는 시간))으로 만듬