Skip to main content

23. Task Scheduler

mediumAsked at Lyft

Minimize total time to execute tasks with a cooldown — Lyft uses the exact same greedy cooling logic to schedule repeated driver-pings so no driver is contacted more frequently than a system-defined interval.

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

Problem

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task, and a non-negative integer n representing the cooldown interval between two same tasks. Return the minimum number of intervals the CPU will take to finish all the tasks. The CPU can be idle during a cooldown interval.

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. Each A and B must be at least 2 apart.

Example 2

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

Approaches

1. Greedy with max-heap simulation

Use a max-heap keyed by task frequency. Each cycle, pick up to n+1 tasks (or pad with idle). Decrement frequencies and re-add non-zero ones. Count total intervals.

Time
O(T * n) where T = tasks.length
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]++;
  freq.sort((a, b) => b - a);

  let time = 0;
  while (freq[0] > 0) {
    let i = 0;
    while (i <= n) {
      if (freq[0] === 0) break;
      if (i < 26 && freq[i] > 0) freq[i]--;
      time++;
      i++;
    }
    freq.sort((a, b) => b - a);
  }
  return time;
}

Tradeoff:

2. Math formula

The answer is max(tasks.length, (maxFreq - 1) * (n + 1) + countOfMaxFreq). The formula computes minimum slots needed by the most-frequent tasks; idle slots fill the rest.

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]++;
  const maxFreq = Math.max(...freq);
  const countMax = freq.filter(f => f === maxFreq).length;
  return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
}

Tradeoff:

Lyft-specific tips

Lyft appreciates candidates who jump straight to the math formula and explain the intuition: 'the most-frequent task governs the frame count; everything else fills in.' If you only code the simulation, the interviewer will ask you to derive the formula. Know both — show the simulation first for correctness, then optimize.

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

Practice these live with InterviewChamp.AI →