# 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

| Item | Meaning |
|---|---|
| Input | `tasks`, a list of uppercase task labels, and `n`, the cooldown |
| Output | The minimum number of intervals needed |
| Task time | Every task takes exactly one interval |
| Idle time | The CPU may be idle if no valid task can run |

Example function shape:

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

## Examples

Example 1:

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

One valid schedule is:

```text
A B idle A B idle A B
```

The answer is:

```python
8
```

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

Example 2:

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

One valid schedule is:

```text
A B C D A B
```

The answer is:

```python
6
```

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

Example 3:

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

One valid schedule is:

```text
A B idle idle A B idle idle A B
```

The answer is:

```python
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:

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

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

```text
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:

```text
(max_freq - 1) groups
```

Each group has:

```text
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:

```python
(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:

```python
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:

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

Return:

```python
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:

```python
(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:

```python
(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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | We count task frequencies, where `m = len(tasks)` |
| Space | `O(1)` | There are only 26 uppercase task labels |

## Implementation

```python
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:

```python
counts = Counter(tasks)
```

For example:

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

gives:

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

Then we find the largest frequency:

```python
max_freq = max(counts.values())
```

Here, `max_freq = 3`.

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

```python
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:

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

For the example:

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

Finally:

```python
return max(len(tasks), frame_length)
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `["A","A","A","B","B","B"]`, `n = 2` | Classic case with idle intervals |
| `["A","C","A","B","D","B"]`, `n = 1` | Other tasks fill the gaps |
| `["A","A","A","B","B","B"]`, `n = 3` | Larger cooldown creates more idle time |
| `["A"]`, `n = 2` | Single task |
| `["A","A","A"]`, `n = 0` | No cooldown |
| `["A","A","A","B","B","B","C","C"]`, `n = 2` | Extra task fills empty slots |