555. Cooldown Scheduler
A print server receives jobs labelled with capital letters in the array tasks; jobs with the same letter are the same kind of job. The server finishes exactly one job per time slot and may also stay idle for a slot, and jobs may be run in any order.
Because the printer needs to cool down, two jobs of the same kind must have at least n other slots (busy or idle) between them. Return the minimum total number of time slots needed to finish every job.
The answer can be far larger than the number of jobs, so simulating slot by slot is too slow. Aim for O(m log 26) time, where m is the number of jobs, using counts of each kind.
Example 1
- Input:
- tasks = ["P","P","P","Q","Q","R"], n = 2
- Output:
- 7
- Explanation:
One optimal order is P Q R P Q _ P: all six jobs plus one idle slot, 7 slots in total.
Example 2
- Input:
- tasks = ["M","N","O"], n = 1
- Output:
- 3
- Explanation:
All three kinds differ, so no cooldown is ever violated and three slots suffice.
Example 3
- Input:
- tasks = ["Z","Z"], n = 3
- Output:
- 5
- Explanation:
The two Z jobs need three slots between them, so the schedule is Z _ _ _ Z: 5 slots.
Constraints
- 1 ≤
tasks.length≤ 105 tasks[i]is an upper-case English letter- 0 ≤
n≤ 104 - The answer is at most about 1.0001 * 109 and fits in a 32-bit integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(m log 26)
- Space
- O(1)