Skip to main content

621. Task Scheduler

mediumAsked at Airbnb

Minimize total time when identical tasks must cool down between runs — Airbnb's host-onboarding pipeline applies this cooling-period logic to ensure the same verification job does not re-run on the same listing until a mandatory review window has passed.

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

Problem

You are given a character array tasks representing CPU tasks and a non-negative integer n representing the cooldown period. Return the minimum number of intervals needed to complete all tasks. During any cooldown, the CPU can be idle.

Constraints

  • 1 <= tasks.length <= 10^4
  • tasks[i] is an 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. Total = 8 intervals.

Example 2

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

Explanation: No cooldown needed; all 6 tasks run back-to-back.

Approaches

1. Greedy simulation with max-heap

Greedily pick the most-frequent available task each cycle. Use a max-heap by frequency and a cooldown queue. Simulate each time unit.

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

function leastInterval(tasks, n) {
  const freq = new Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
  const heap = new MaxHeap();
  for (const f of freq) if (f > 0) heap.push(f);
  let time = 0;
  const cooldown = [];
  while (heap.size() || cooldown.length) {
    time++;
    if (heap.size()) {
      const f = heap.pop() - 1;
      if (f > 0) cooldown.push([f, time + n]);
    }
    if (cooldown.length && cooldown[0][1] === time) {
      heap.push(cooldown.shift()[0]);
    }
  }
  return time;
}

Tradeoff:

2. Math formula (O(1) extra space)

The minimum time is determined by the most-frequent task. Formula: max(tasks.length, (maxFreq-1)*(n+1) + countOfMaxFreq). Constant space, no simulation.

Time
O(T)
Space
O(1)
function leastInterval(tasks, n) {
  const freq = new Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
  freq.sort((a, b) => b - a);
  const maxFreq = freq[0];
  let countOfMax = 0;
  for (const f of freq) { if (f === maxFreq) countOfMax++; else break; }
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countOfMax);
}

Tradeoff:

Airbnb-specific tips

Airbnb interviewers love the formula approach because it shows mathematical intuition — but start by explaining the simulation to build trust. The key insight: idle slots only appear when the cooldown for the most-frequent task forces waiting; otherwise other tasks fill the gaps. Draw out a frame diagram before coding to make the formula derivation obvious to your interviewer.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →