Skip to main content

18. Task Scheduler

mediumAsked at Asana

Compute the minimum CPU intervals needed to execute tasks with a cooldown constraint — Asana's scheduling engine faces this exact problem when rate-limiting repeated task-type assignments across a team's sprint.

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

Problem

You are given a character array tasks representing CPU tasks and an integer n representing the cooldown interval between two same tasks. 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 an uppercase English letter
  • 0 <= n <= 100

Examples

Example 1

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

Explanation: One valid schedule: A B idle A B idle A B — 8 intervals.

Example 2

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

Explanation: No cooldown — finish all 6 tasks back-to-back.

Approaches

1. Greedy with frequency count

The most-frequent task drives the frame count. Compute partitions = (maxFreq - 1), idle slots = partitions * n - (otherTasks), total = max(tasks.length, total with idles).

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 maxFreq = freq[0];
  let idleSlots = (maxFreq - 1) * n;

  for (let i = 1; i < freq.length && freq[i] > 0; i++) {
    idleSlots -= Math.min(freq[i], maxFreq - 1);
  }

  idleSlots = Math.max(0, idleSlots);
  return tasks.length + idleSlots;
}

Tradeoff:

2. Max-heap simulation (priority queue)

Use a max-heap to always schedule the highest-frequency remaining task. Track cooldown via a wait queue keyed by the next-available time.

Time
O(T * log 26) = O(T)
Space
O(26) = O(1)
function leastInterval(tasks, n) {
  const freq = new Map();
  for (const t of tasks) freq.set(t, (freq.get(t) || 0) + 1);

  // Simple max-heap via sorted array (26 letters — bounded size)
  let counts = [...freq.values()].sort((a, b) => b - a);
  let time = 0;
  const cooldown = []; // [nextAvailableTime, count]

  while (counts.length > 0 || cooldown.length > 0) {
    time++;
    if (counts.length > 0) {
      const top = counts.shift();
      if (top - 1 > 0) cooldown.push([time + n, top - 1]);
    }
    // Release cooled-down tasks back to the heap
    const ready = cooldown.filter(([t]) => t === time);
    for (const [, cnt] of ready) {
      counts.push(cnt);
      counts.sort((a, b) => b - a);
    }
    cooldown.splice(0, cooldown.length, ...cooldown.filter(([t]) => t !== time));
  }

  return time;
}

Tradeoff:

Asana-specific tips

Asana grades how well you map abstract scheduling constraints to a concrete algorithm. The greedy formula answer is fast and clean — be ready to derive it from first principles (frame size = n+1 tasks per partition). Interviewers also ask the simulation variant to see if you can build a priority queue from scratch. Naming 'greedy frame packing' vs 'max-heap simulation' shows you know the pattern family.

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

Practice these live with InterviewChamp.AI →