Task Scheduler

Problem in Plain English

Given tasks labeled A through Z and a cooldown n forcing identical tasks at least n intervals apart, arrange every task into the shortest schedule that may include idle slots. Return that minimum total interval count.

Problem Statement

Given a list of tasks tasks where each entry is an uppercase letter, and a cooldown integer n, schedule every task on a CPU that handles one task or one idle slot per interval.

Between consecutive executions of the same letter, at least n complete intervals must pass, while different tasks may run back to back in any order.

Return the smallest possible total number of intervals, counting both work and idle time.

Constraints

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

Examples

Example 1

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

One best order is A -> B -> idle -> A -> B -> idle -> A -> B, which keeps two intervals between equal letters.

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

With no cooldown, any order works, for example A -> A -> A -> B -> B -> B, so no idle slot is needed.

Example 3

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16

One best order is A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A.

Intuition

Repeated letters, rather than task order, force the idle time. In Example 1, three copies of A need two gaps of two intervals; B fills one interval in each gap but cannot fill both because B also has a cooldown. A heap can simulate the schedule one interval at a time. Counting the largest frequency and how many letters share it gives the same minimum without constructing the schedule.

Approaches

Cooldown Simulation

Solution Details

Reveal Cooldown Simulation: intuition, complexity, and code

Intuition

Execute the currently available letter with the most copies remaining, then park its remaining count in a FIFO cooldown queue. Serving a frequent letter early starts its next cooldown early; when no letter is available, the current interval must be idle. Counts suffice because every letter has the same cooldown and only the total duration is requested.

Step-by-Step Logic

Count each letter and place positive remaining counts in a max heap. Keep a FIFO queue of [remaining, releaseAfter] entries. Example 1 starts with counts A: 3, B: 3, an empty queue, and time 0.
Advance time by one. If the heap is nonempty, execute its maximum count and decrement it; if copies remain, enqueue them with releaseAfter = time + n. In Example 1, running A at time 1 parks its count 2 until the end of interval 3.
If no count is available, spend the current interval idle. Example 1 runs B at time 2 and idles at time 3 because both letters are cooling.
After running or idling, release the queue front whose releaseAfter equals time into the heap. Releasing A after interval 3 lets it run at 4, preserving two intervening intervals; for n = 0, release happens immediately after its own execution.
Repeat until both structures are empty. Example 1 runs A, B, idle, A, B, idle, A, B and returns time 8. Heap ties may choose either letter; the length is unchanged.

Why It Works

Each unfinished letter has exactly one entry: either its remaining count in the heap or its count and release time in the queue. After execution at time t, the entry is released only after interval t + n, so its next execution is no earlier than t + n + 1. Release times increase with execution times, making a FIFO queue sufficient. Greedily prioritizing the largest available remaining count balances the longest chains of repeated letters: postponing a shorter chain cannot create more required cooldown gaps than postponing a longer one. Equivalently, this rule fills cooldown frames with the most frequent unfinished letters before using spare letters. A frame needs idle intervals only when no unfinished letter is available. Thus it realizes the frequency-frame lower bound described in the next approach, and never adds an avoidable trailing idle after the last task. Together with the valid-cooldown invariant, this establishes the minimum duration.

Dry Run

Cooldown Simulation: variable states at each step
`time`	run	heap after	queue after
`1`	`A`	`[3]`	`[[2 till 3]]`
`2`	`B`	`[]`	`[[2 till 3], [2 till 4]]`
`3`	idle	`[2]`	`[[2 till 4]]`
`4`	`A`	`[2]`	`[[1 till 6]]`
`5`	`B`	`[]`	`[[1 till 6], [1 till 7]]`
`6`	idle	`[1]`	`[[1 till 7]]`
`7`	`A`	`[1]`	`[]`
`8`	`B`	`[]`	`[]`, return `8`

Complexity Analysis

Time Complexity

O(T(n + 1))

Space Complexity

O(1)

Let T be tasks.length and n be the cooldown. A schedule lasts at most (T - 1)(n + 1) + 1 intervals; each interval does constant work because the heap and queue each hold at most 26 letter entries. JavaScript shift also moves at most 26 entries. Thus the parameterized bound is O(T(n + 1)), including n = 0; with the stated n <= 100 it simplifies to O(T). The frequency table, heap and queue have constant peak auxiliary space and no schedule is allocated. Queue records are created O(T) times over the whole execution, but only O(26) are live at once. Maximum duration is 1009900, safely within Java int and JavaScript exact integer range.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Collections;3import java.util.PriorityQueue;4import java.util.Queue;5
6class Solution {7    public int leastInterval(char[] tasks, int n) {8        int[] counts = new int[26];9        for (char c : tasks) counts[c - 'A']++;10        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());11        for (int count : counts) {12            if (count > 0) maxHeap.offer(count);13        }14        Queue<int[]> wait = new ArrayDeque<>();15        int time = 0;16        while (!maxHeap.isEmpty() || !wait.isEmpty()) {17            time++;18            if (!maxHeap.isEmpty()) {19                // Largest remaining count starts the longest pending chain first.20                int left = maxHeap.poll() - 1;21                if (left > 0) wait.offer(new int[]{left, time + n});22            }23            // Release AFTER this interval: the next run is time + 1.24            if (!wait.isEmpty() && wait.peek()[1] == time) {25                maxHeap.offer(wait.poll()[0]);26            }27        }28        return time;29    }30}

Hints

Hint 1

The most frequent task sets the shape of the whole schedule, so start by counting frequencies and naming the maximum.

Hint 2

Picture the top task splitting time into maxFreq - 1 blocks of n + 1 slots each, with the other top tasks filling the tail.

Hint 3

Idle slots only matter when the block frame outgrows the task list, so the answer is the larger of the frame size and tasks.length.

Edge Cases

n = 0 removes every cooldown, so any order works and the answer is exactly tasks.length.
Enough distinct tasks to fill every gap, like many letters with n = 2, also needs zero idle time.
A single repeated task, such as six copies of A with n = 2, forces maximum idle: five width-3 gaps plus a final A give 16 intervals.
One task returns 1 even with n = 100; never add a cooldown after the final task.
More than n + 1 letters tied for maximum frequency makes the frame smaller than the actual task count; return T.

Common Mistakes and Interview Tips

Returning the frame size without comparing against tasks.length, which undercounts when the cooldown is tiny.
Counting only one task at the top frequency and forgetting maxCount, which drops the tail slots of tied tasks.
In the simulation, releasing cooled tasks before running the current slot, which lets a task run one interval too early.
Using O(T * n) as the simulation bound gives zero work when n = 0; use O(T(n + 1)).
Treating each queued execution as a permanent entry overstates peak space: a letter is in exactly one structure, and the alphabet has only 26 letters.
Interview tip: explain both lower bounds, T and (f - 1)(n + 1) + k, before applying the formula.

Key Takeaway

Cooldown schedules are won by serving the highest remaining frequency first; when only the shape of the answer matters, the most frequent item often yields a closed-form frame.