Task Scheduler

Difficulty: Medium Source: NeetCode

Problem

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: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of CPU intervals required to complete all the 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","A","A","B","B","B"], n = 0 Output: 6

Constraints:

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter
• 0 <= n <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — always scheduling the most frequent available task
• Max-heap — extracting the task with the highest remaining count
• Cooldown queue — tracking when a task becomes available again

1. Brute Force — Math Formula

Intuition

Think about the most frequent task (say task A appears max_count times). It creates max_count - 1 “frames” of size n + 1, plus a final slot. Any other tasks slot into these frames. If there are more tasks than frames can hold, we don’t need any idle time — the answer is just len(tasks). Otherwise the formula gives us the minimum intervals.

Algorithm

1. Count the frequency of each task.
2. Find max_count = highest frequency.
3. Count how many tasks share that max frequency (num_max).
4. Return max(len(tasks), (max_count - 1) * (n + 1) + num_max).

Solution

from collections import Counter

def leastInterval(tasks, n):
    counts = Counter(tasks)
    max_count = max(counts.values())
    num_max = sum(1 for c in counts.values() if c == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + num_max)


print(leastInterval(["A","A","A","B","B","B"], 2))  # 8
print(leastInterval(["A","A","A","B","B","B"], 0))  # 6
print(leastInterval(["A","A","A","A","B","B"], 2))  # 8 → A-B-idle-A-B-idle-A-idle-idle-A

Complexity

• Time: O(n) where n = number of tasks
• Space: O(1) — at most 26 distinct task types

2. Greedy Max-Heap with Cooldown Queue

Intuition

Simulate the CPU cycle by cycle. At each step, pick the available task with the highest remaining count (that’s the greedy choice — reduce the bottleneck). After running a task, it enters a cooldown queue and becomes available again after n intervals. If no task is available, we idle. This approach is more verbose than the formula but explicitly models the scheduling process.

Algorithm

1. Count frequencies, build a max-heap (negate counts).
2. Use a deque cooldown storing (count, available_at_time).
3. Simulate time t = 0, 1, 2, ...: a. If cooldown has a task ready at time t, push it back onto the heap. b. If the heap is non-empty, pop the most frequent task, run it (decrement count), and if count > 0, add (count, t + n + 1) to the cooldown queue. c. Increment t.
4. Return t.

Solution

import heapq
from collections import Counter, deque

def leastInterval(tasks, n):
    counts = Counter(tasks)
    # Max-heap via negation
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)

    cooldown = deque()  # (negative_remaining_count, available_at_time)
    t = 0

    while heap or cooldown:
        # Release tasks whose cooldown has expired
        if cooldown and cooldown[0][1] <= t:
            heapq.heappush(heap, cooldown.popleft()[0])

        if heap:
            count = heapq.heappop(heap) + 1  # increment because count is negative
            if count < 0:  # still has remaining runs
                cooldown.append((count, t + n + 1))
        # else: idle this cycle

        t += 1

    return t


print(leastInterval(["A","A","A","B","B","B"], 2))  # 8
print(leastInterval(["A","A","A","B","B","B"], 0))  # 6
print(leastInterval(["A","A","A","A","B","B"], 2))  # 10

Complexity

• Time: O(t) where t is the total intervals (bounded by O(tasks * n))
• Space: O(1) — at most 26 task types in heap and queue

Common Pitfalls

Forgetting the max(len(tasks), formula) in the math approach. When tasks are diverse and n is small, there’s no idle time and the answer is simply the number of tasks. The formula can undercount in that case.

Simulation: not checking the cooldown queue before idling. If you forget to check whether the cooldown has released a task before declaring an idle cycle, you’ll over-count intervals.

Off-by-one on cooldown availability. A task run at time t is available again at time t + n + 1, not t + n. The cooldown lasts n intervals after the task runs, so n + 1 total steps later.