> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Task Scheduler Python Solution with Tests

> Tested Python solution for LeetCode 621 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 621, Medium. Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting. [View on LeetCode](https://leetcode.com/problems/task-scheduler/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 621   # by problem number
lcpy gen -s task_scheduler   # by problem name
```

## 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: there has to be a gap of **at least** `n` intervals between two tasks with the same label.

Return the **minimum** number of CPU intervals required to complete all tasks.

### Examples

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

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

```
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
```

**Explanation:** A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

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

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/task_scheduler/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/task_scheduler/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq
from collections import Counter, deque


class Solution:
    # Time: O(T * n + m log m) where T = len(tasks), worst case with many idle periods
    # Space: O(m) where m ≤ 26, so O(1)
    def least_interval(self, tasks: list[str], n: int) -> int:
        counts = Counter(tasks)
        max_heap = [-count for count in counts.values()]
        heapq.heapify(max_heap)

        step_num = 0
        queue: deque[tuple[int, int]] = deque()  # (count, available_time)

        while max_heap or queue:
            step_num += 1

            while queue and queue[0][1] <= step_num:
                count, _ = queue.popleft()
                heapq.heappush(max_heap, count)

            if max_heap:
                count = heapq.heappop(max_heap)
                count += 1  # Decrease count (was negative)
                if count < 0:  # Still has tasks left
                    queue.append((count, step_num + n + 1))

        return step_num


class SolutionGreedy:
    # Time: O(T + m) where T = len(tasks), m = unique tasks ≤ 26, so O(T)
    # Space: O(m) where m ≤ 26, so O(1)
    def least_interval(self, tasks: list[str], n: int) -> int:
        """
        Mathematical approach:

        Key insight: The most frequent task determines the minimum time.

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

        1. Find max frequency: max_freq = 3 (A and B both appear 3 times)
        2. Count tasks with max frequency: max_count = 2 (A and B)
        3. Create frame structure:
           Frame: A B _ | A B _ | A B
           - (max_freq - 1) complete frames of size (n + 1)
           - Last frame contains only max frequency tasks

        4. Calculate minimum intervals:
           - Frame intervals: (max_freq - 1) * (n + 1) = 2 * 3 = 6
           - Plus max frequency tasks: 6 + 2 = 8

        5. Return max(total_tasks, calculated_min) to handle cases where
           we have enough variety to fill all gaps without idle time.
        """
        counts = Counter(tasks)
        max_freq = max(counts.values())
        max_count = sum(1 for freq in counts.values() if freq == max_freq)

        # Minimum intervals needed based on most frequent tasks
        min_intervals = (max_freq - 1) * (n + 1) + max_count

        # Return max to handle cases with sufficient task variety
        return max(len(tasks), min_intervals)
```

## Complexity

| Time                                                                        | Space                      |
| --------------------------------------------------------------------------- | -------------------------- |
| O(T \* n + m log m) where T = len(tasks), worst case with many idle periods | O(m) where m ≤ 26, so O(1) |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).