Task Scheduler

Problem

https://leetcode.com/problems/task-scheduler/

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there’s a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

Example 3:

Input: tasks = ["A","A","A","B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

Constraints:

• 1 <= tasks.length <= 10⁴

• tasks[i] is an uppercase English letter.

• 0 <= n <= 100

Pattern

Heap, Greedy, Hash Table

Approaches

Greedy

Explanation

Observe two things: 1. We want to schedule more frequent tasks first as we can fit in less frequent tasks during the cooldown period. 2. We want round robin tasks to avoid idling later during the cooldown period by too quickly exhausting the pool of unscheduled tasks. Thus the optimal schedule will round robin the tasks from most frequent to least frequent, idling when needed to respect the cooldown period.

First, count the frequency of each task and then sort in descending order by the frequency. While there are stil tasks remaining, loop through the tasks and decrease the count by 1 to indicate that the task is being run. If we did not exhaust all the tasks and we have not reached the cooldown period, wait until the cooldown period has passed. This completes one round robin. Repeat until we have completed every task.

Code

from collections import Counter


def leastInterval(tasks: list[str], n: int) -> int:
    """Return the minimum intervals to finish all tasks."""
    counter = Counter(tasks)
    result = 0

    while counter:
        most_common = counter.most_common()
        m = min(n + 1, len(most_common))
        for i in range(m):
            result += 1
            task, _ = most_common[i]
            counter[task] -= 1
            if counter[task] == 0:
                del counter[task]

        if counter and n + 1 > m:
            result += n + 1 - m

    return result

Test

>>> from task_scheduler__greedy import leastInterval
>>> leastInterval(["A","A","A","B","B","B"], 2)
8
>>> leastInterval(["A","C","A","B","D","B"], 1)
6
>>> leastInterval(["A","A","A","B","B","B"], 3)
10

Complexity

\(T\) is the number of tasks and \(n\) is the cooldown period

Measure	Complexity	Notes
Time	\(O(T)\)	must decrement count for every task
Auxiliary Space	\(O(T)\)	task counter dictionary

task_scheduler__greedy.leastInterval(tasks: list[str], n: int) → int

Return the minimum intervals to finish all tasks.

Max Heap

Code

import heapq
from collections import Counter, deque


def leastInterval(tasks: list[str], n: int) -> int:
    """Return the minimum intervals to finish all tasks."""
    counter = Counter(tasks)
    heap = [-count for count in counter.values()]
    heapq.heapify(heap)

    time = 0
    cooldown: deque[tuple[int, int]] = deque()

    while heap or cooldown:
        time += 1

        if not heap:
            time = cooldown[0][1]
        else:
            count = heapq.heappop(heap) + 1
            if count < 0:
                cooldown.append((count, time + n))

        if cooldown and cooldown[0][1] == time:
            heapq.heappush(heap, cooldown.popleft()[0])

    return time

Test

>>> from task_scheduler__max_heap import leastInterval
>>> leastInterval(["A","A","A","B","B","B"], 2)
8
>>> leastInterval(["A","C","A","B","D","B"], 1)
6
>>> leastInterval(["A","A","A","B","B","B"], 3)
10

task_scheduler__max_heap.leastInterval(tasks: list[str], n: int) → int

Return the minimum intervals to finish all tasks.