Problem 481293 · medium · Level 04 Non-Linear Data Structures

CPU Cooldown Schedule

heaps · greedy · scheduling · counting

A CPU must run a list of tasks, each a single uppercase letter naming its type, one task per time slot in any order. After running a task of some type, the CPU must wait at least n slots before running another task of the same type; it may run other types or stay idle in between.

Return the minimum number of time slots needed to finish every task.

Examples

Input:  tasks = ["A", "A", "A", "B", "B", "B"], n = 2
Output: 8
Explanation: A B idle A B idle A B.

Input:  tasks = ["A", "A", "A", "B", "B", "B"], n = 0
Output: 6

Input:  tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: A B C A D E A F G A idle idle A idle idle A.

Constraints

  • 1 <= len(tasks) <= 10**5, 0 <= n <= 100
  • Target complexity: O(m log m) per round of scheduling, or O(n) with a counting argument; both are accepted.

Goals

  • Model a cooldown constraint with a max-heap of remaining counts
  • Schedule in rounds of n + 1 slots, idling when nothing is runnable
  • Count total elapsed slots including idle ones
Starting Python…