621. Task Scheduler

Problem¶

Given task letters and a cooldown n, each same letter must be separated by at least n intervals.

Return the minimum total intervals, counting both work and idle slots.

Example:

tasks = [A,A,A,B,B,B], n = 2
answer = 8
schedule = A B idle A B idle A B

Key trick¶

Count frequencies, then build the answer from the most frequent task.

The minimum is:

\[ \max\left(\text{len(tasks)},\ (max\_freq - 1)(n + 1) + count\_max\right) \]

where:

max_freq is the largest task count
count_max is how many task types have that largest count

Trap¶

Using simulation when a counting formula is enough.
Forgetting the final answer cannot be smaller than len(tasks).
Mishandling ties when several tasks share the maximum frequency.
Off-by-one on cooldown spacing.

Why is it interesting?¶

It looks like scheduling, but the best solution is a frequency-counting observation.

It tests whether you can replace simulation with a tight counting argument in \(O(n)\) time.

Python solution¶

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        # Count task frequencies.
        freqs = {}
        for task in tasks:
            freqs[task] = freqs.get(task, 0) + 1

        # Highest frequency among all task types.
        max_freq = max(freqs.values())

        # How many task types reach that highest frequency.
        cnt_max = 0
        for cnt in freqs.values():
            if cnt == max_freq:
                cnt_max += 1

        # Think of placing the most frequent tasks first:
        # (max_freq - 1) full blocks of size (n + 1),
        # then the last occurrences of all max-frequency tasks.
        slots_needed = (max_freq - 1) * (n + 1) + cnt_max

        # If there are enough other tasks to fill idle gaps,
        # the answer is just the total number of tasks.
        return max(len(tasks), slots_needed)

Complexity:

Time: \(O(n)\)
Space: \(O(1)\) because there are at most 26 task types

Comment on my solution¶

Your solution is correct and the state modeling is clear.

Main issue:

You re-sort remaining tasks every interval, so it is slower than needed.

Small note:

next_allowed_interval_to_run is a bit tricky to reason about because of the < interval check and interval + n update, even though it works.
For this problem, the frequency formula is much simpler and faster than simulation.

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        # task -> (how_many_left, next_allowed_interval_to_run)
        # next_allowed_time_to_run = 0 means can be run anytime
        remaining_tasks = {}
        for task in tasks:
            if task in remaining_tasks:
                remaining_tasks[task][0] += 1 # increment task count
            else:
                remaining_tasks[task] = [1, -1]

        interval = 0

        while remaining_tasks:
            remaining = sorted(remaining_tasks, key=lambda t: remaining_tasks[t][0], reverse=True)
            for task in remaining:
                if remaining_tasks[task][1] < interval:
                    remaining_tasks[task][0] -= 1
                    remaining_tasks[task][1] = interval + n
                    if remaining_tasks[task][0] == 0:
                        del remaining_tasks[task]
                    break
            # One task completed or idle once
            interval += 1

        return interval