Heaps Simulating with a heap
415. Task Scheduler
You are given a string tasks and an integer cooldown. Each letter of tasks is one task to run, and
equal letters are copies of the same task.
A CPU works in units of time. In each unit it either runs one task or stays idle. After a task runs, the same
task cannot run again until cooldown more units have passed, so two copies of a task always have at least
cooldown units between them. Different tasks can run one right after the other, and the tasks can run in
any order.
Return the smallest number of units the CPU needs to run every task.
Example 1
Input: tasks = "AAABBC", cooldown = 2
7Explanation: One best order is A, B, C, A, B, idle, A. There are two units between any two A's. A has three copies, so no order fits in 6 units.
Example 2
Input: tasks = "AABBCCDE", cooldown = 2
8Explanation: The order A, B, C, D, A, B, C, E needs no idle unit, so the answer is the number of tasks.
Example 3
Input: tasks = "AAAA", cooldown = 1000000000
3000000004Explanation: Each A has to wait 109 units after the one before it. The A's run at units 1, 109 + 2, 2 × 109 + 3 and 3 × 109 + 4.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ tasks.length ≤ 105tasksholds only the uppercase lettersAtoZ.0 ≤ cooldown ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.