악곱 == 악성곱슬

정렬, 우선순위 큐

---

이 문제는 디스크를 “대기 시간이 가장 적도록” 우선순위를 배치하여 실행시키는 문제이다.

대기 시간이 가장 적으려면 매 초, 매 순간 정렬을 통해 가장 먼저 끝낼 수 있는 태스크를 빨리 끝내는게 관건이다. 그러나 매 순간 정렬을 한다는 것은 시간적으로 비효율적이다.

따라서 가장 먼저 끝날 수 있는 태스크, 즉 runtime이 가장 적은 태스크를 key로 하는 우선순위 큐(min-heap)을 사용하면 쉽게 구현할 수 있다.

알고리즘은 다음과 같다.

1. 작업(jobs 배열)을 시작 시간 기준으로 정렬(내림차순). → deque를 import 하지 않고 list의 pop 메서드를 사용하기 위해 역순으로 정렬했다.
2. heap, jobs가 빌 때까지 반복한다.
   1. 만약 heap만 비어있다면 1초 증가하고 2로 돌아감
   2. heap에서 하나 pop 하고 현재 시간에 해당 작업의 runtime을 더한다.
   3. 총 대기 시간에 해당 작업이 기다린 시간을 더한다.(현재 시간 + 요청 시간)
3. 작업의 개수대로 나누어 반환

구현

---

import heapq

def solution(jobs):
    jobs.sort(reverse=True)
    job_cnt = len(jobs)
    cur_time = 0
    heap = []
    # 시작 시간 초기화
    answer = 0
    while True:
        # 시간에 맞게 들어오는 요청을 모두 heap 에 넣는다.
        while True:
            if jobs and jobs[-1][0] <= cur_time:
                req_time, runtime = jobs.pop()
                heapq.heappush(heap, (runtime, req_time))
                continue
            break
        # 반복문 탈출 조건
        if not heap:
            if not jobs:
                break
            cur_time += 1
            continue
        # heap 에서 원소 하나 빼서 일을 진행한다
        runtime, req_time = heapq.heappop(heap)
        cur_time += runtime
        answer += (cur_time - req_time)
    return answer // job_cnt

print(solution([[0, 3], [1, 9], [2, 6]]))
print(solution([[1, 3], [2, 3]]))
print(solution([[8, 3], [0, 10], [0, 14]]))