Skip to main content

621. Task Scheduler

mediumAsked at Amazon

Given a list of tasks and cooldown n, return the minimum time to finish all tasks where the same task can't run within n steps of itself. Amazon asks this to test whether you reach for the greedy 'fill slots from most-frequent task' formula.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as the scheduling / greedy round.
  • Blind (2025-11)— Recurring Amazon interview problem.

Problem

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array). Return the least number of units of times that the CPU will take to finish all the given tasks.

Constraints

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

Examples

Example 1

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

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B

Example 2

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

Approaches

1. Greedy formula (optimal)

Count tasks. Find the max count M. There are (n + 1) * (M - 1) + (# tasks with count == M) frames. Answer is max(this, len(tasks)).

Time
O(n)
Space
O(1)
function leastInterval(tasks, n) {
  const counts = new Array(26).fill(0);
  for (const t of tasks) counts[t.charCodeAt(0) - 65]++;
  let maxCount = 0;
  let tied = 0;
  for (const c of counts) {
    if (c > maxCount) { maxCount = c; tied = 1; }
    else if (c === maxCount) tied++;
  }
  const frame = (n + 1) * (maxCount - 1) + tied;
  return Math.max(frame, tasks.length);
}

Tradeoff: Constant-time formula. The most-frequent task fixes the lower bound; ties contribute one extra slot each. If tasks.length exceeds this frame, we don't need idles.

2. Max-heap simulation (alternative)

Push (count, task) into max-heap. Each cycle: pop up to n+1 tasks; emit and decrement; push back. Track total time.

Time
O(n * k log k)
Space
O(k)
class MaxHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { if (!this.data.length) return; const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p] >= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this.data[l] > this.data[best]) best = l; if (r < this.data.length && this.data[r] > this.data[best]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

function leastIntervalHeap(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;
  while (heap.size()) {
    const cycle = [];
    for (let i = 0; i < n + 1; i++) {
      if (heap.size()) cycle.push(heap.pop());
    }
    for (const c of cycle) if (c - 1 > 0) heap.push(c - 1);
    time += heap.size() ? n + 1 : cycle.length;
  }
  return time;
}

Tradeoff: More intuitive simulation. Useful to whiteboard if you don't immediately see the formula.

Amazon-specific tips

Amazon interviewers want the formula version. State out loud: 'Imagine drawing frames of size n+1. The most-frequent task fills M-1 complete frames plus its final slot. Ties contribute one slot per tied task. If the total tasks fit in fewer than that many frames, we use len(tasks).' That framing is the senior-IC signal.

Common mistakes

  • Forgetting to take max with tasks.length — without it, you'd output the idle-padded answer even when no idles are needed.
  • Off-by-one with maxCount - 1 (the last frame holds only the final occurrence of each tied task).
  • Treating tied count as 1 (it's the number of tasks with count == maxCount, including the most-frequent one).

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • What if the cooldown were variable per task?
  • What if you wanted the actual schedule, not just the time?
  • Reorganize String (LC 767) — special case where n = 1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Where does the formula come from?

Draw the most-frequent task M times. Between each pair of consecutive occurrences, you need n slots filled by other tasks (or idles). That's M-1 frames of size n+1 = (M-1)(n+1) slots. Add the final task occurrences = +tied.

Why is max with tasks.length necessary?

If there are many distinct tasks, you may not need idles at all. The formula assumes idles fill gaps; max enforces 'no more time than the number of tasks if we don't need idles.'

Practice these live with InterviewChamp.AI

Drill Task Scheduler and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →