Skip to main content

20. Task Scheduler

mediumAsked at CircleCI

Compute the minimum time to execute CPU tasks with a cooldown period — directly analogous to CircleCI's job scheduling with resource constraints and cooldown between same-type jobs.

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

Problem

Given a list of CPU tasks labeled A-Z and a cooldown integer n, return the minimum number of intervals to finish all tasks. Tasks of the same type must be at least n intervals apart; idle intervals are allowed.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Greedy frequency formula

Use math: (max_freq - 1) * (n + 1) + count_of_max_freq_tasks, taking max with tasks.length.

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]++;
  freq.sort((a, b) => b - a);
  const maxF = freq[0];
  let maxCount = freq.filter(f => f === maxF).length;
  return Math.max(tasks.length, (maxF - 1) * (n + 1) + maxCount);
}

Tradeoff:

2. Max-heap simulation

Simulate the scheduler tick-by-tick using a max-heap of (frequency, taskType) pairs and a cooldown queue, demonstrating how a real dispatcher would work.

Time
O(n log 26) = O(n)
Space
O(26)
function leastInterval(tasks, n) {
  const freq = {};
  for (const t of tasks) freq[t] = (freq[t] || 0) + 1;
  // Max-heap via sorted array (small input, 26 letters max)
  let heap = Object.values(freq).sort((a, b) => b - a);
  let time = 0;
  while (heap.length) {
    const cycle = n + 1;
    const temp = [];
    let i = 0;
    while (i < cycle && heap.length) {
      const top = heap.shift();
      if (top > 1) temp.push(top - 1);
      i++; time++;
    }
    heap.push(...temp);
    heap.sort((a, b) => b - a);
    if (heap.length) time += cycle - i;
  }
  return time;
}

Tradeoff:

CircleCI-specific tips

CircleCI loves this problem because it models their executor concurrency limits — articulate the greedy formula first, then describe how the heap simulation generalizes to real job dispatchers with priority queues.

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

Practice these live with InterviewChamp.AI →