medium

Task Scheduler

Find the minimum time needed to finish a list of tasks with a required cooldown between repeats.

1. Define the problem

Task Scheduler

Given an array of CPU tasks, each labeled by a letter, and an integer n representing the required cooldown between two occurrences of the same task, return the minimum number of intervals needed to finish all tasks. A CPU may sit idle if no task is eligible yet. The most-frequent task drives the answer : space it out by its required cooldown, and any idle slots left over get filled by other tasks or otherwise stay idle.

Constraints

  • 1 ≤ tasks.length ≤ 104
  • tasksi is an uppercase English letter
  • 0 ≤ n ≤ 100

Example

Inputtasks = ["A", "A", "A", "B", "B", "B"], n = 2
Output8

Explanation One valid order is A, B, idle, A, B, idle, A, B — 8 intervals, respecting the cooldown of 2 for each letter.

2. Know the words first

In plain terms

Cooldown
The minimum number of intervals that must pass before the same task letter can run again.
3. Visualize the solution

Space out the most frequent tasks by the cooldown

Space out the most frequent tasks by the cooldown
StatusmaxCount=3

Both A and B occur 3 times — that is the highest frequency in this task list.

What happens in this step

freq: A = 3, B = 3

maxCount = max(3, 3) = 3 — both A and B tie for the highest frequency in this task list.
Step 1 of 4

Steps to visualize

  1. Count how often each task letter appears.
  2. Find the highest count, and how many different letters share that highest count.
  3. The busiest tasks need (maxCount - 1) full cooldown rows, plus one slot per tied task in the final row.
  4. The answer is whichever is larger: that reserved slot count, or simply the total number of tasks.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Space out the most frequent tasks by the cooldown
StatusmaxCount=3

Both A and B occur 3 times — that is the highest frequency in this task list.

What happens in this step

freq: A = 3, B = 3

maxCount = max(3, 3) = 3 — both A and B tie for the highest frequency in this task list.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function leastInterval(tasks, n) {
  const freq = new Map();
  for (const task of tasks) {
    freq.set(task, (freq.get(task) ?? 0) + 1);
  }

  const counts = [...freq.values()];
  const maxCount = Math.max(...counts);
  const maxCountTasks = counts.filter((count) => count === maxCount).length;

  return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxCountTasks);
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
tasks = ["A", "A", "A", "B", "B", "B"], n = 28example from the docstring
tasks = ["A", "A", "A", "B", "B", "B"], n = 06no cooldown means tasks can run back to back
tasks = ["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"], n = 216one task dominates heavily while others just fill idle slots
tasks = ["A", "A", "A"], n = 27only one task type, forcing idle slots for the full cooldown
tasks = ["A", "B", "C", "D"], n = 24every task is different, so no cooldown ever applies
tasks = ["A", "A", "B", "B"], n = 04zero cooldown always equals the raw task count
tasks = ["A"], n = 51smallest valid input, a single task with no repeats to space out

Keep reading