Skip to main content

16. Task Scheduler

mediumAsked at Redis

Compute the minimum CPU cycles to execute tasks with a cool-down constraint; Redis uses it to probe scheduling logic that mirrors expiration sampling in cron.c.

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

Problem

Given a list of task labels and a non-negative integer n representing the cool-down between same-type tasks, return the minimum number of intervals required to finish all tasks. Each interval is 1 unit of CPU.

Constraints

  • 1 <= tasks.length <= 10^4
  • 0 <= n <= 100

Examples

Example 1

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

Example 2

Input
tasks=["A","C","A","B","D","B"], n=1
Output
6

Approaches

1. Simulate with priority queue

At each tick pick the highest-count available task; track last-used tick per type.

Time
O(T log U)
Space
O(U)
// Min-heap by next-eligible tick, sim until done.

Tradeoff:

2. Math: fill idle slots formula

Count frequencies, let maxF and tieCount be the max frequency and how many tasks share it. Answer = max(tasks.length, (maxF - 1) * (n + 1) + tieCount). This closed-form is faster than simulation.

Time
O(T)
Space
O(1)
function leastInterval(tasks, n) {
  const counts = new Array(26).fill(0);
  for (const t of tasks) counts[t.charCodeAt(0) - 65]++;
  const maxF = Math.max(...counts);
  const tieCount = counts.filter(c => c === maxF).length;
  return Math.max(tasks.length, (maxF - 1) * (n + 1) + tieCount);
}

Tradeoff:

Redis-specific tips

Redis interviewers reward you for spotting the closed-form because it's how serverCron in Redis avoids per-key wall-clock scans; mention activeExpireCycle's amortized sampling.

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

Practice these live with InterviewChamp.AI →