Task Scheduler

Examples

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

One valid order is A -> B -> idle -> A -> B -> idle -> A -> B, which takes 8 time units. Any A must wait 2 units after the previous A, and the same for B.

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

With no cooldown at all, the tasks can just run back-to-back in any order, taking exactly as long as there are tasks.

Constraints

• 1 <= tasks.length <= 10^4

• tasks[i] is an uppercase English letter

• 0 <= n <= 100

Approach

The task that occurs most often is the bottleneck: it forces gaps of at least n between its own repeats, and everything else has to fit around those gaps (or the schedule idles if nothing fits).

One way to build a valid schedule is a greedy simulation with a max-heap: at each time unit, run whichever eligible task (one that isn't still cooling down) currently has the most instances left, tracking tasks in cooldown in a separate queue until they become eligible again.

A faster counting argument skips the simulation entirely. Let maxFreq be the highest count any single task has, and numMax be how many different tasks share that highest count. Picture the most frequent task's repeats as dividers, each followed by an n-wide gap: that creates (maxFreq - 1) * (n + 1) + numMax "slots" that must be filled by other tasks or idle time. The answer is whichever is larger: that slot count, or simply the total number of tasks (since you can never finish faster than one time unit per task).

Solutions

Greedy Simulation - Max-Heap + Cooldown Queue

Count how many times each task letter appears. At every time tick, run the most frequent eligible task (tracked in a max-heap), and put it in a cooldown queue until n more ticks have passed, at which point it becomes eligible again.

class MaxHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[i] > this.data[parent]) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < n && this.data[left] > this.data[largest]) largest = left;
        if (right < n && this.data[right] > this.data[largest]) largest = right;
        if (largest === i) break;
        [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
        i = largest;
      }
    }
    return top;
  }
}

function leastInterval(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);

  const heap = new MaxHeap();
  for (const c of counts.values()) heap.push(c);

  let time = 0;
  const cooldownQueue = []; // entries: [remainingCount, timeItBecomesEligibleAgain]

  while (heap.size() > 0 || cooldownQueue.length > 0) {
    time++;

    if (heap.size() > 0) {
      const remaining = heap.pop() - 1;
      if (remaining > 0) cooldownQueue.push([remaining, time + n]);
    }

    if (cooldownQueue.length > 0 && cooldownQueue[0][1] === time) {
      heap.push(cooldownQueue.shift()[0]);
    }
  }

  return time;
}

Time: O(n) - at most 26 task types, so heap operations are O(log 26) = O(1); the number of ticks simulated is bounded by the final answer · Space: O(1) - at most 26 entries across the heap and cooldown queue

Optimal - Counting Formula

Find the task with the highest frequency and how many tasks tie for that frequency. That determines the minimum number of slots needed around the most frequent task's repeats; compare that to simply running every task back-to-back.

function leastInterval(tasks, n) {
  const counts = new Array(26).fill(0);
  for (const t of tasks) counts[t.charCodeAt(0) - 65]++;

  const maxFreq = Math.max(...counts);
  const numMax = counts.filter((c) => c === maxFreq).length;

  const slots = (maxFreq - 1) * (n + 1) + numMax;
  return Math.max(tasks.length, slots);
}

Time: O(n) - one pass to count task frequencies (26 letters is treated as constant) · Space: O(1) - a fixed 26-entry count array