Task Scheduler

Medium Subject: Heap / Priority Queue

Time Complexity

O(T * N)

Space Complexity

O(N)

Problem Description

Problem Statement

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks. Return the least number of units of time the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

Optimal Solution

Python

Approach: Max Heap and Queue

Count frequencies. The most frequent task dictates the minimum time. We use a max heap to process tasks. We pop a task, process it, and put it in a cooldown queue with the time it can be executed again. When time - n == queue[0][0], we push it back to the heap.

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

        time = 0
        q = deque() # pairs of (time, count)

        while max_heap or q:
            time += 1
            if max_heap:
                cnt = 1 + heapq.heappop(max_heap)
                if cnt != 0:
                    q.append((time + n, cnt))
            if q and q[0][0] == time:
                heapq.heappush(max_heap, q.popleft()[1])

        return time