프로그래머스: 디스크 컨트롤러

Priority Queue를 이용하면 쉽게 풀 수 있다.

알고리즘은 '대기 큐에 들어온 Task 중 수행 시간이 가장 짧은 Task를 먼저 처리한다'가 답이다.

이는 운영체제 CPU 스케줄링 방식 중 하나인 SJF (Shortest Job First)와 유사하다.

SJF가 궁금하다면, https://focalpoint.tistory.com/96?category=918151 

쉽게 배우는 운영체제 내용 정리 - Chapter 04 CPU 스케줄링

import heapq

def solution(jobs):
    answer = 0
    length = len(jobs)
    heapq.heapify(jobs)
    # 현재 시각
    t = 0
    # [소요 시간, 요청 시각]
    pq = []
    while jobs:
        # 요청 시각 <= t인 작업들을 priority_queue에 삽입
        while True:
            while jobs and jobs[0][0] <= t:
                job = heapq.heappop(jobs)
                heapq.heappush(pq, [job[1], job[0]])
            if pq:
                break
            else:
                t += 1
        # Task 처리
        dur, rt = heapq.heappop(pq)
        t += dur
        answer += t - rt
    # pq 잔챙이 처리
    while pq:
        dur, rt = heapq.heappop(pq)
        t += dur
        answer += t - rt
    return answer // length