Marauder Bot

Problem

You are given a list of tasks, each labeled by type, and a cooldown value n: the same task type cannot run again until n other time units have passed since its last run, and idling counts toward this gap if no other task is ready. Each task takes one unit of time. Return the minimum total time units needed to finish every task.

Example. With tasks [A, A, A, B, B, B] and n = 2, one valid schedule is A, B, idle, A, B, idle, A, B, taking 8 time units total.

Key idea

The bottleneck is always the most frequent task type, since it forces the longest stretches of cooldown. Count how often each type appears and focus on the highest count, call it maxCount. That type needs maxCount runs spaced n apart, carving the timeline into (maxCount - 1) full cooldown windows of length (n + 1), plus one final run at the end.

Other task types fill the idle gaps of those windows in order of decreasing frequency. With enough variety to fill every gap, the total time is just the task count, with no idling; otherwise the unfilled gaps become idle time. The frame estimate is (maxCount - 1) × (n + 1) plus however many types tie for maxCount. Taking the larger of that and the plain task count gives the answer directly, with no schedule needed.

Solution

function leastInterval(tasks: string[], n: number): number {
  const counts = new Array<number>(26).fill(0);
  for (const task of tasks) {
    counts[task.charCodeAt(0) - 'A'.charCodeAt(0)]++; // bucket by task letter A-Z
  }

  const maxCount = Math.max(...counts);
  const maxCountTies = counts.filter((count) => count === maxCount).length; // types that need a slot in the final window

  const frame = (maxCount - 1) * (n + 1) + maxCountTies; // idle-frame lower bound built around the busiest task
  return Math.max(frame, tasks.length); // enough variety fills idle gaps, so never go below the raw task count
}

Complexity

Time: O(m). One pass to count task frequencies, where m is the number of tasks; a fixed-size table for task types keeps counting O(1) per type.
Space: O(1). The frequency table is bounded by the fixed number of task types.

Watch out for

The idle-frame formula only applies when there is not enough variety to fill every gap; always take the max with the plain task count, since abundant variety can make idling unnecessary.
Ties for the maximum frequency matter: every task type tied for maxCount needs its own slot in the final partial window.

Pattern

This is a greedy scheduling problem where the bottleneck resource sets a structural lower bound, and the rest of the input either fits inside that structure for free or extends it. The same "let the busiest resource set the frame" reasoning recurs in interval and resource-allocation scheduling.

Task Scheduler