Skip to main content

621. Task Scheduler

mediumAsked at Bloomberg

Bloomberg's batch-job infrastructure schedules thousands of daily data-refresh tasks under cooldown constraints between repeated runs — this problem captures that scheduling logic and tests whether you can compute minimum total time using a greedy frequency analysis instead of simulation.

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

Problem

Given an array tasks of CPU task types (characters A-Z) and a cooldown integer n, each task takes 1 unit of time and the same task type must wait at least n intervals before running again. The CPU can be idle. Return the minimum number of intervals needed to finish all tasks.

Constraints

  • 1 <= tasks.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. Total 8 intervals.

Example 2

Input
tasks = ['A','A','A','A','A','A','B','C','D','E','F','G'], n = 2
Output
16

Approaches

1. Simulation with greedy frequency sort

Use a frequency array of 26 task types. Greedily execute up to n+1 tasks per cycle (most-frequent first), sort after each cycle. O(N) amortized since at most 26 distinct tasks.

Time
O(N * n) worst case
Space
O(1) since only 26 task types
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);
  let time = 0;
  while (freq[0] > 0) {
    let i = 0;
    for (let slot = 0; slot <= n; slot++) {
      if (freq[0] === 0) break;
      if (i < freq.length && freq[i] > 0) { freq[i]--; i++; }
      time++;
    }
    freq.sort((a, b) => b - a);
  }
  return time;
}

Tradeoff:

2. Greedy formula (optimal O(N))

The bottleneck is the most-frequent task. It creates (maxFreq - 1) full cycles of length (n + 1), plus a final partial cycle of width equal to the count of tasks sharing the max frequency. The answer is max(tasks.length, formula).

Time
O(N)
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;
  const formula = (maxFreq - 1) * (n + 1) + maxCount;
  return Math.max(tasks.length, formula);
}

Tradeoff:

Bloomberg-specific tips

Bloomberg interviewers use this problem to test two things simultaneously: whether you can spot a greedy formula and whether you can justify it rigorously. Walk through why the answer is max(tasks.length, ...) — when n is small, tasks are dense enough that idle slots disappear and the total equals tasks.length. When n is large, the most-frequent task drives padding. Bloomberg's scheduling teams deal with exactly this tradeoff when batching end-of-day report generation jobs under regulatory cooldown windows.

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

Practice these live with InterviewChamp.AI →