jobs | return |
---|---|
[[0, 3], [1, 9], [2, 6]] | 9 |
현재 시점에서 처리할 수 있는 작업들을 모아 놓고 하나를 뽑아 현재 시점과 총 대기시간을 구해주는 것을 반복
- 작업의 소요 시간 기준으로 최소힙을 만든다.
- 현재 시점에서 처리할 수 있는지의 여부는, 작업의 요청 시간이 이전에 완료한 작업의 시작 시간과 현재 시점 사이에 있어야한다.
- 만약 현재 처리할 수 있는 작업이 없다면 남아있는 작업들의 요청 시간이 아직 오지 않았으므로 현재 시점을 업해준다.
import heapq
def solution(jobs):
q = []
ans, i = 0, 0
prev_start = -1 # 이전 시작 시각
current = 0 # 현재 시각
while i < len(jobs):
for start, period in jobs:
# 이전 작업의 시작과 현재 사이에 시작할 수 있는 작업이 있으면 힙에 넣어준다.
if prev_start < start <= current:
# 작업이 걸리는 기간이 짧은 순대로 진행해야하므로
heapq.heappush(q, (period, start))
# 현재 시작할 수 있는 작업이 있는 경우
if len(q) > 0:
# 작업 시작
now_p, now_s = heapq.heappop(q)
prev_start = current # 현재가 이전이 되고
current += now_p # 지금 시각에 걸리는 시간 더하고 = 현재
ans += (current-now_s) # 현재에서 시작했던 시간을 빼면 작업하는데에 걸린 시간
i += 1
else:
# 작업할 게 당장 없으면 시간만 간다
current += 1
return int(ans/len(jobs))