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

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

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.