MediumArrayHash TableGreedySortingHeap (Priority Queue)Counting

Task Scheduler

1 approach, code in every language

You are given an array of CPU tasks, each labelled with an uppercase letter, and an integer n that represents the cooldown period. Two identical tasks must be separated by at least n time units, during which the CPU may either run a different task or stay idle.

Every task takes exactly one time unit. Return the minimum number of time units the CPU needs to finish all of the tasks, inserting idle slots wherever they are unavoidable.

Example 1

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

Output: 8

One valid ordering is A B idle A B idle A B. The three A's are each two units apart, and so are the three B's, giving 8 total units.

Example 2

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

Output: 6

There are enough distinct tasks to keep the CPU busy, so no idle slots are needed and the answer equals the number of tasks.

Constraints

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

Greedy Frame Counting

Derive the answer from the most frequent task using a closed-form frame formula.

Loading animation…

Intuition

The task that appears the most often is the bottleneck of the whole schedule. If the maximum frequency is f, we must place those f copies at least n apart, which carves the timeline into f - 1 mandatory frames of width n + 1, followed by a final short row. Any task that also reaches the maximum frequency adds one more slot to that final row, giving the length (f - 1) * (n + 1) + maxCount. When there are many distinct tasks, the idle gaps get completely filled and the schedule length is simply the number of tasks. Taking the maximum of the two candidates yields the answer without simulating the timeline. A max-heap simulation would give the same result: at each step you pop the highest-count available task and hold used tasks in a cooldown window of size n + 1.

Algorithm walkthrough

1Count the frequency of every task label using a fixed 26-slot array.
2Scan the counts to find the maximum frequency f.
3Count how many task labels share that maximum frequency (maxCount).
4Compute the mandatory frame length: (f - 1) * (n + 1) + maxCount.
5If the number of tasks exceeds this frame length, the idle slots are all filled, so the answer is the total number of tasks.
6Return the maximum of the frame length and the total task count.

Implementation

from typing import List
from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks)
        max_freq = max(counts.values())
        max_count = sum(1 for c in counts.values() if c == max_freq)
        frame = (max_freq - 1) * (n + 1) + max_count
        return max(len(tasks), frame)

Time

O(N)

Space

O(1)

Counting the N tasks dominates; the frequency table is bounded to 26 slots, so extra space is constant. The closed-form formula avoids any explicit timeline simulation.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Press Die Cooldown is our own problem on the technique behind Task Scheduler: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free