📖 힙(Heap) > 디스크 컨트롤러
- 1번에 1작업만 가능
📖What I thought
- 요청-종료 평균 시간의 최소 → 최대한 덜 기다려야 함(작업 시간은 못 바꾸므로) → 요청-종료 시간이 짧은 것부터 처리
- 근데 작업이 한 번에 들어오는 게 아니야 → 현재시간(대기+작업) - 들어온 시점을 뺀 값이 요청-종료 시간 가장 짧은 시간임
현재시간 : 이 전 작업 끝난 시점 or 거기에 +1 씩 계속 더해간 값(끝났는데 대기열에 요청 작업 없음) == 총 소요 시간 들어온 시점 : 대기열에 올라옴
- 어쨌든 그 값의 최솟값을 계속 접근해야하니까 우선순위 큐(heapq) 쓰자!
📖풀이
📎heapq
import heapq
def solution(jobs):
avr, st, now, fin = 0, -1, 0, 0 # 작업물 처리 시간 총합, 이전 작업 완료 시간, 현재시간, 끝난 작업 수
hq = []
while fin != len(jobs):
for job in jobs:
if st < job[0] <= now:
heapq.heappush(hq, (job[1], job[0]))
if len(hq) > 0:
cur = heapq.heappop(hq)
# 정보 갱신
st = now # 시작 시간 → 현재 시간
now += cur[0] # 현재 시간 → 작업 수행 시간 더해주기
avr += now - cur[1] # 작업 완료 시간 - 대기 시간
fin += 1
else:
now += 1
return avr // len(jobs)