Cooldown Scheduler
MediumHeap / Priority Queue
Problem
A single build agent runs jobs in unit-length time slots. Each entry of tasks is one job, labelled by an uppercase letter; jobs with the same letter are the same kind. In each slot the agent either runs exactly one pending job or sits idle.
After running a job of some kind, the agent must wait at least n slots before running another job of the same kind. Jobs may run in any order. Return the minimum number of slots needed to run every job.
Example 1
- Input:
- tasks = ["A", "A", "A", "B", "B", "C"], n = 2
- Output:
- 7
A B C A B idle A: the three As need two slots between them, which B, C and one idle slot fill.
Example 2
- Input:
- tasks = ["A", "B", "C", "A"], n = 0
- Output:
- 4
Example 3
- Input:
- tasks = ["A", "A", "A"], n = 3
- Output:
- 9
A idle idle idle A idle idle idle A.
Constraints
- 1 ≤ tasks.length ≤ 10^4
- tasks[i] is an uppercase English letter
- 0 ≤ n ≤ 100
Hint
Show the first hint
Which kind of job is most dangerous to leave for last?
Walkthrough
How to approach it
01Clarify before coding
- Does the cooldown apply across different kinds? No, only between jobs of the same letter.
- Is n the number of slots strictly between two same-kind jobs? Yes: with n = 2, A at slot 1 allows the next A at slot 4.
- Can we reorder freely? Yes, any order.
02Brute force
Search over all orders (or DP over remaining counts and last-run times) and keep the shortest valid schedule.
Cost: Exponential in the number of jobs; even memoised state over 26 counts plus cooldown timers explodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.