[DSA][Heap] 05. Task Scheduler

LeetCode 621

 

05. Task Scheduler

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n.
Each CPU interval can be idle or allow the completion of one task.
Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

 

 

[아이디어]

- max heap을 사용하여 가장 빈도수가 높은 task부터 처리하고, queue에 남은 개수와 재처리가 가능한 시간 (Current Time + n)을 저장하여 해당 시간이 되면 다시 heap에 넣는다.

 

 

[풀이 1] Max Heap

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = Counter(tasks)
        maxHeap = [-cnt for cnt in count.values()]
        heapq.heapify(maxHeap)

        time = 0
        q = deque() # pairs of [-cnt, idleTime]
        while maxHeap or q:
            time += 1
            if not maxHeap:
                time = q[0][1]
            else:
                cnt = 1 + heapq.heappop(maxHeap) # cnt - 1
                if cnt:
                    q.append([cnt, time + n]) # idle until (time + n)
            if q and q[0][1] == time: # idleTime finish
                heapq.heappush(maxHeap, q.popleft()[0])
        
        return time

 

가장 효율적으로 CPU를 사용하기 위해서는 가장 높은 빈도를 가진 task부터 우선 처리하는 게 유리하다. 빈도가 높다는 건 동일한 task가 여러 개 있다는 의미이고, 그 사이에 최소 n번의 idle이 있어야 하기 때문에 우선 처리한 후 중간에 다른 task를 끼워 넣어 idle을 최소화해야 한다.

 

이를 위해 먼저 tasks의 각 task에 대한 빈도수를 저장하는 count map을 만들고, 이 빈도를 기반으로 max-heap을 구성한다. 이 heap에서 가장 빈도가 높은 task를 꺼내 처리한 후, 해당 task는 재사용하기 위해 시간 n만큼 기다려야 하므로, queue에 남은 빈도와 함께 다시 사용할 수 있는 시점 (현재 시간 + n)을 저장한다.

 

만약 heap이 비었다면, 현재는 처리할 수 있는 task가 없다는 뜻이고, 그 말은 곧 cooldown 중인 task만 남아 있다는 의미다. 이때 다시 task를 처리하려면 두 가지를 고려해야 한다.

[1] 남은 task 중에서 가장 높은 빈도를 가진 task를 선택해야 한다는 점
→ 이건 문제가 되지 않는다. 처음부터 가장 큰 빈도의 task부터 heap에 넣고 처리했기 때문에, 각 task의 빈도는 1씩 줄어들고, queue에서도 자연스럽게 가장 앞에 있는 task가 가장 높은 빈도를 가진 task임이 보장된다.

 

[2] 해당 task의 cooldown (idle) 시간이 끝났는지 확인해야 한다는 점
→ queue에 저장할 때 task를 다시 사용할 수 있는 시점(time + n) 도 함께 저장해 뒀기 때문에, 현재 시간이 그 시점 이상인지 비교하면 된다.

 

시간(time)은 기본적으로 1씩 증가시키면서 진행하지만, 만약 heap이 비어 있고, queue에 있는 task들도 아직 cooldown 중이라면, 굳이 1씩 증가시킬 필요 없이, queue 가장 앞에 있는 task의 사용 가능 시점으로 바로 점프할 수 있다. 이렇게 하면 불필요한 idle 시간을 줄이면서 훨씬 더 효율적으로 스케줄링할 수 있다.

 

 

⏱️ 시간복잡도

전체 task의 개수를 T라 하면, 모든 task를 다 처리할 때까지 연산을 반복하므로 전체 시간 복잡도는 O(T + n)에 비례한다. (n은 idleTime)

🧠 공간복잡도

count map, max-heap, queue에는 모두 task의 종류 수 (최대 26개)만큼만 값이 저장되므로, 입력 크기에 관계없이 상수 공간만 사용한다. 따라서 공간 복잡도는 O(1)이다.