621. Task Scheduler

hardAsked at Snap

Snap's filter-rendering pipeline processes tasks with mandatory cooldowns between same-type GPU operations — task scheduler is the exact scheduling problem that capacity planning team models.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given a character array tasks (each task is CPU work identified by a letter A-Z) and a non-negative integer n (cooldown between identical tasks), return the minimum number of intervals (CPU units) needed to finish all tasks. CPU can be idle during cooldown.

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

Example 2

Input

tasks = ["A","A","A","B","B","B"], n = 0

Output

Approaches

1. Greedy simulation with max-heap

Use a max-heap keyed by frequency. Each 'round' of n+1 slots: pop up to n+1 tasks (most frequent first), decrement counts, re-add those with count > 0 after the round. If heap has fewer than n+1 tasks, the rest of the round is idle time. Time O(time * log(26)) = O(time).

Time: O(tasks.length * n)
Space: O(1) — at most 26 task types

function leastInterval(tasks, n) {
  const freq = new Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
  // Max-heap via sorted array (26 elements max — sort is fine)
  let time = 0;
  while (true) {
    freq.sort((a, b) => b - a);
    let rounds = 0;
    for (let i = 0; i <= n; i++) {
      if (freq[i] > 0) {
        freq[i]--;
        rounds++;
      }
    }
    if (freq.every(f => f === 0)) { time += rounds; break; }
    time += n + 1;
  }
  return time;
}

Tradeoff:

2. Math formula (O(n))

Let maxFreq = highest task frequency, maxCount = number of tasks with that frequency. The minimum time is max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount). This formula captures: either tasks fill the slots naturally, or the most-frequent task forces idle slots. O(tasks.length) single pass.

Time: O(tasks.length)
Space: O(1)

function leastInterval(tasks, n) {
  const freq = new Array(26).fill(0);
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
  const maxFreq = Math.max(...freq);
  const maxCount = freq.filter(f => f === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}

Tradeoff:

Snap-specific tips

Snap's follow-up: 'What if cooldown applies to a class of tasks, not just identical ones?' That breaks the formula — you need the greedy heap simulation. Be ready to derive the formula from scratch: draw the grid for maxFreq rows of (n+1) columns, explain why idle slots are forced, and count the last partial row.

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 Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →