[LeetCode] Single-Threaded CPU (Python)

LeetCode Single-Threaded CPU

그리디알고리즘을 활용해서 해결했다. 문제를 해결하는 포인트는 다음과 같았다.

1. 두 가지 조건을 고려해야 한다.
   • 프로세스가 시작할 수 있는 시간이 현재 시간보다 작거나 같아야 한다.
   • 실행 가능한 프로세스 중에선 실행 시간이 짧은 것을 선택한다.
2. 이러한 조건들을 편하게 확인하기 위해서 두 개의 힙을 만들고 첫번째 힙에서 조건을 충족하는 힙을 pop하고 두번째 힙으로 push한다.
3. 힙1에는 요소가 남아있지만, 힙2에는 요소가 남아있지 않다면, 시간을 조정한다.(시간이 그대로 흐르기 때문)

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        res = []
        stage = []
        t = 0
        for i in range(len(tasks)):
            tasks[i].append(i)
        heapq.heapify(tasks)
        while tasks or stage:
            if not stage and t < tasks[0][0]:
                t = tasks[0][0]
            while tasks and tasks[0][0] <= t:
                heapq.heappush(stage, [tasks[0][1], tasks[0][2]])
                heapq.heappop(tasks)
            pTime, idx = heapq.heappop(stage)
            t += pTime
            res.append(idx)
        return res