Task Scheduler

Problem

A CPU must execute a list of tasks, given as an array of uppercase letters where each letter is a task type. Each task takes one time unit. The CPU may run any task or sit idle in a given unit. Two tasks of the same type must be separated by at least n other units (tasks of other types or idle slots). Tasks may be executed in any order. Return the minimum total number of time units needed to finish everything.

• Between 1 and 50,000 tasks, each labelled with one of the 26 uppercase letters.
• The cooldown n is between 0 and 1,000.

Examples

• tasks = ["C", "C", "C", "C", "D", "D"], n = 2 → 10. One valid schedule: C D idle C D idle C idle idle C.
• tasks = ["X", "Y", "X", "Y", "Z"], n = 1 → 5. Three distinct types and a cooldown of one mean some off-cooldown task is always available, so no idle time is needed.
• tasks = ["P", "P", "P", "P", "Q", "R", "S"], n = 3 → 13. The four Ps force three gaps of three slots each, and the other three tasks fill only the first gap.

Hints

1. Which task type determines the minimum length of the schedule? What is the smallest possible span between the first and last copy of that type?
2. Lay out the most frequent task with exactly n slots between copies. How many empty slots does that create, and what can fill them?
3. Either simulate greedily with a max-heap on remaining counts and a cooldown queue, or compute (max_freq - 1) * (n + 1) + (number of task types with max_freq) and take the max with len(tasks).