Task Scheduler

A single processor has to run a list of jobs, tasks, where each job is labelled with an uppercase letter. Jobs with the same label are the same kind of work, and every job takes exactly one time unit.

In each time unit the processor either runs one job or sits idle. Jobs may be run in any order, but there is a cool-down rule: after a job with some label runs, at least n time units must pass before another job with the same label can run.

Return the minimum number of time units needed to finish every job, counting idle units.

Example 1

Example 2

Example 3

Constraints

• 1 <= tasks.length <= 104
• tasks[i] is an uppercase English letter
• 0 <= n <= 100

Pattern Path · Intervals & Greedy · problem 112 of 169

Start simple

Simulate time step by step, each step picking the available job with the most remaining copies (scanning all labels): correct but O(T · 26) where T includes idle steps.

The key idea

Count how many times each label appears, and let maxCount be the largest count and tied the number of labels that have it.

Picture the schedule as rows of width n + 1. A most frequent label must start a new row each time it runs, so there are maxCount - 1 full rows followed by a last, partial row. That last row holds only the labels that also occur maxCount times, so its length is tied. This frame has length (maxCount - 1) · (n + 1) + tied, and no schedule can be shorter, because the top label alone forces that much time.

Every other job can be dropped into the empty slots of the full rows, filling them column by column so equal labels stay at least n + 1 apart. If there are more jobs than empty slots, the rows simply grow wider and no idling is needed at all, so the answer is the number of jobs. Therefore:

answer = max(len(tasks), (maxCount - 1) · (n + 1) + tied)

A max-heap simulation (each round of n + 1 slots, run the most frequent remaining labels) gives the same result and is a fine alternative to present.

Complexity

• Time: O(T)
• Space: O(1) (26 counters)

Python

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        counts = Counter(tasks).values()
        max_count = max(counts)
        tied = sum(1 for c in counts if c == max_count)
        # (max_count - 1) full rows of width n + 1, then a last row of the tied labels.
        frame = (max_count - 1) * (n + 1) + tied
        return max(len(tasks), frame)

JavaScript

var leastInterval = function(tasks, n) {
  const counts = new Map();
  for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
  const maxCount = Math.max(...counts.values());
  let tied = 0;
  for (const c of counts.values()) if (c === maxCount) tied++;
  // (maxCount - 1) full rows of width n + 1, then a last row of the tied labels.
  const frame = (maxCount - 1) * (n + 1) + tied;
  return Math.max(tasks.length, frame);
};

What the interviewer is checking

The interviewer wants to see you reason about the bottleneck greedily, and either derive the counting formula or build a correct heap-based simulation and explain why it is optimal.

Mistakes to avoid

• Forgetting that several labels can tie for the highest count, which lengthens the last row.
• Not taking the maximum with len(tasks); when there are many distinct labels no idling is needed.
• Treating n as the distance between starts instead of the number of units in between (the gap is n + 1).

Follow-ups to expect

• Return an actual schedule, not just its length? (Max-heap plus cool-down queue.)
• What if the jobs must run in the given order? (Track next allowed time per label.)
• What if each label had its own cool-down? (Simulation with a heap by ready time.)

In real software

CPU and job schedulers, API rate limiters that cap how often one client can be served, and DRAM refresh scheduling all spread out repeated work under a cool-down constraint.

Practice next