Skip to main content

621. Task Scheduler

mediumAsked at DoorDash

Given tasks and a cooldown n, return the minimum CPU intervals needed. DoorDash uses this for backend scheduling rounds — the same shape appears in courier dispatch with cooldowns between assignments.

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list Task Scheduler as a recurring greedy + heap question.
  • Blind (2025-12)— DoorDash backend SDE reports note the O(1) math formula as the actual senior signal.

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), that is that there must be at least n units of time between any two same tasks. 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 upper-case English letter.
  • The integer n is in the range [0, 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","C","A","B","D","B"], n = 1
Output
6

Example 3

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

Approaches

1. Math formula (optimal O(n))

Find max frequency f. Count tasks tied at max as t. Answer = max(tasks.length, (f-1) * (n+1) + t).

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

Tradeoff: DoorDash's preferred answer. The insight: lay out the most-frequent task in a grid with (n+1) per row; idle slots are bounded by the gaps. Cleanly O(n), no heap, no scheduling sim.

2. Max-heap simulation

Max-heap of frequencies. Each interval pops up to n+1 top frequencies, decrements them, idles the rest. Count time.

Time
O(N log 26)
Space
O(1)
function leastIntervalHeap(tasks, n) {
  const count = new Map();
  for (const t of tasks) count.set(t, (count.get(t) || 0) + 1);
  const heap = [...count.values()];
  heap.sort((a, b) => b - a);
  let time = 0;
  while (heap.length) {
    const batch = [];
    for (let i = 0; i <= n; i++) {
      if (heap.length) batch.push(heap.shift() - 1);
      time++;
      if (!heap.length && batch.every((x) => x === 0)) return time;
    }
    for (const b of batch) if (b > 0) heap.push(b);
    heap.sort((a, b) => b - a);
  }
  return time;
}

Tradeoff: Direct simulation. Easier to explain but more code. Mention as the alternative if you blank on the formula.

DoorDash-specific tips

DoorDash interviewers grade specifically on whether you DERIVE the math formula. Sketch a grid of (n+1) columns; show how the max-frequency task pins the row count to f. State this on the whiteboard BEFORE coding.

Common mistakes

  • Forgetting the max(tasks.length, ...) cap — if there are MANY distinct tasks, no idle slots are needed.
  • Counting how many tasks share the max frequency incorrectly (it determines the trailing partial row).
  • Confusing n (cooldown) with the row width (n+1).

Follow-up questions

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

  • Reorganize String (LC 767) — same pattern with a string output instead of a count.
  • Rearrange String k Distance Apart (LC 358) — string variant of cooldown.
  • Task Scheduler II (LC 2365) — minimum days with cooldown per task type.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why the math formula?

Imagine the (n+1)-wide grid where each column slots one occurrence of the max-frequency task. Idle slots fill the remaining columns; ties at max frequency pad the last row.

Why max(tasks.length, formula)?

If there are enough distinct tasks to fill every slot, no idle is needed — total time = tasks.length. The formula only matters when idle slots dominate.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →