DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Task Scheduler

mediumHeaps and top-K

Problem statement

A job runner receives a list of jobs, each labelled with an uppercase letter that names its type. Every job takes exactly one time unit. After a job of some type runs, another job of the same type must wait until at least n time units have passed; jobs of other types can run in between. When nothing is allowed to run, the runner sits idle for a unit.

You may run the jobs in any order. Return the smallest number of time units (jobs plus idle slots) needed to finish all of them.

Examples

Example 1

Input: tasks = ["B", "B", "B", "C", "C"], n = 2

Output: 7

Explanation: One best order is B C idle B C idle B. The three B jobs need two full gaps of width 2 between them.

Example 2

Input: tasks = ["X", "Y", "Z", "X", "Y", "Z"], n = 1

Output: 6

Explanation: X Y Z X Y Z never repeats a type within one unit, so no idle slot is needed.

Hints

Approach

You do not need to build the schedule to know its length. Let f be the highest frequency and k the number of types that have that frequency.

Lay out the most frequent type first: its f jobs form f - 1 blocks of width n + 1 (the job plus n slots after it), followed by a final row. The final row holds one job from each of the k most frequent types. That frame has length (f - 1) * (n + 1) + k. Every other job fits into the gaps of the frame without breaking the cooldown.

If there are more jobs than gaps, the frame is already full and the extra jobs just stretch it with no idle time at all, so the answer is len(tasks).

  1. Count each type.
  2. Find f and k.
  3. Return max(len(tasks), (f - 1) * (n + 1) + k).
ComplexityTime O(m), where m = len(tasks)Space O(1)
Python
from collections import Counter
class Solution:
def leastInterval(self, tasks: list[str], n: int) -> int:
counts = Counter(tasks).values()
top = max(counts)
tied = sum(1 for c in counts if c == top)
frame = (top - 1) * (n + 1) + tied
return max(len(tasks), frame)

Follow-up questions

  • Return the actual schedule, with idle in the empty slots, not just its length.
  • Jobs must now run in the given order (no reordering). How long does that take? A dictionary of last-run times gives it in one pass.

Frequently asked questions

When there are many distinct types, the gaps in the frame fill up and some jobs are left over. Those jobs can be spread across the rows without ever creating an idle slot, so the schedule is exactly as long as the job count, which can be larger than the frame.

The largest pile is the one that will run out of partners to fill its gaps. Running it as early and as often as the cooldown allows spreads it out, which is the same insight the formula captures in closed form.

Any scheduler with a per-key cooldown has this shape: not restarting the same service twice within a minute, rate limiting calls per API key, or spacing out deploys to the same cluster. The frame argument is a quick way to estimate the minimum total time.