LeetCode 621: Task Scheduler

Problem Restatement

We are given a list of CPU tasks. Each task is represented by a capital letter from A to Z.

Each task takes exactly one CPU interval.

The CPU can do one of two things in each interval:

1. Execute one task.
2. Stay idle.

There is also a non-negative integer n. This means that between two executions of the same task, there must be at least n intervals.

We may reorder the tasks in any way. Return the minimum number of CPU intervals needed to finish all tasks.

Input and Output

Example function shape:

def leastInterval(tasks: list[str], n: int) -> int:
    ...

Examples

Example 1:

tasks = ["A", "A", "A", "B", "B", "B"]
n = 2

One valid schedule is:

A B idle A B idle A B

The answer is:

8

The same task must wait for 2 intervals before it can appear again.

Example 2:

tasks = ["A", "C", "A", "B", "D", "B"]
n = 1

One valid schedule is:

A B C D A B

The answer is:

6

There is no idle time because other tasks can fill the cooldown gaps.

Example 3:

tasks = ["A", "A", "A", "B", "B", "B"]
n = 3

One valid schedule is:

A B idle idle A B idle idle A B

The answer is:

10

First Thought: Simulate the CPU

A natural approach is to simulate the process.

At every interval, choose the most frequent task that is not cooling down. If no task is available, add an idle interval.

This can be implemented with a max heap and a queue for cooldown tasks.

That approach works, but this problem has a simpler counting solution because task labels are only uppercase letters. We do not need to build the actual schedule. We only need its minimum length.

Key Insight

The tasks that appear most often determine the minimum possible schedule length.

Suppose the most frequent task appears max_freq times.

For example:

tasks = ["A", "A", "A", "B", "B", "B"]
n = 2

Task A appears 3 times. If we place the A tasks first, we get:

A _ _ A _ _ A

There are max_freq - 1 gaps between the most frequent tasks.

Each gap must have length at least n.

So the basic frame has:

(max_freq - 1) groups

Each group has:

n + 1 slots

The +1 is for the most frequent task itself.

Then we add the final occurrences of all tasks that also have the maximum frequency.

The formula is:

(max_freq - 1) * (n + 1) + max_count

where max_count is the number of task labels that appear max_freq times.

Finally, the answer cannot be smaller than the number of tasks, because every task takes one interval.

So the final answer is:

max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Algorithm

Count the frequency of each task.

Find the largest frequency, called max_freq.

Count how many tasks have this frequency. Call this max_count.

Compute the minimum schedule frame:

frame_length = (max_freq - 1) * (n + 1) + max_count

Return:

max(len(tasks), frame_length)

We take the maximum because there are two cases.

If there are not enough other tasks to fill the cooldown gaps, we need idle intervals.

If there are enough other tasks, then no idle intervals are needed, and the answer is just len(tasks).

Correctness

Let max_freq be the largest number of times any task appears.

Choose one task with this frequency. Its occurrences must be separated by at least n intervals.

Therefore, before its final occurrence, we need max_freq - 1 separated blocks. Each block must have size at least n + 1: one slot for this frequent task, followed by at least n slots before the same task may appear again.

This gives the lower bound:

(max_freq - 1) * (n + 1)

If several task labels have the same maximum frequency, their final occurrences must all be placed at the end of this frame. If max_count tasks share the maximum frequency, the frame length becomes:

(max_freq - 1) * (n + 1) + max_count

So no valid schedule can be shorter than that frame.

Also, no valid schedule can be shorter than len(tasks), because each task takes one interval.

Thus the answer must be at least:

max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

This length is achievable. We place the most frequent tasks as anchors, then fill the gaps with all other tasks as much as possible. If there are not enough tasks, the remaining slots become idle. If there are enough tasks, they fill all gaps and may extend the schedule, but then the total length is exactly len(tasks).

Therefore the formula gives the minimum possible number of intervals.

Complexity

Implementation

from collections import Counter
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)

        max_freq = max(counts.values())
        max_count = sum(1 for count in counts.values() if count == max_freq)

        frame_length = (max_freq - 1) * (n + 1) + max_count

        return max(len(tasks), frame_length)

Code Explanation

We first count how many times each task appears:

counts = Counter(tasks)

For example:

tasks = ["A", "A", "A", "B", "B", "B"]

gives:

{"A": 3, "B": 3}

Then we find the largest frequency:

max_freq = max(counts.values())

Here, max_freq = 3.

Next we count how many task labels have that same frequency:

max_count = sum(1 for count in counts.values() if count == max_freq)

Here, both A and B appear 3 times, so max_count = 2.

Then we compute the frame length:

frame_length = (max_freq - 1) * (n + 1) + max_count

For the example:

(3 - 1) * (2 + 1) + 2 = 8

Finally:

return max(len(tasks), frame_length)

This handles both cases: schedules with idle time and schedules without idle time.

Testing

def run_tests():
    s = Solution()

    assert s.leastInterval(["A", "A", "A", "B", "B", "B"], 2) == 8
    assert s.leastInterval(["A", "C", "A", "B", "D", "B"], 1) == 6
    assert s.leastInterval(["A", "A", "A", "B", "B", "B"], 3) == 10
    assert s.leastInterval(["A"], 2) == 1
    assert s.leastInterval(["A", "A", "A"], 0) == 3
    assert s.leastInterval(["A", "A", "A", "B", "B", "B", "C", "C"], 2) == 8

    print("all tests passed")

run_tests()

Test meaning: