A CPU has to run a list of tasks. Each task is an uppercase letter from A to Z; equal letters are copies of the same task. Running one task takes one unit of time, and in each unit the CPU either runs one task or stays idle.
There is a cooldown: two copies of the same task must be at least n units apart, so after running a task the CPU needs n other units (other tasks, or idle) before it can run that task again. The tasks can run in any order.
Return the fewest units of time the CPU needs to run all the tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: One best order is A B idle A B idle A B. After an A, two other units must pass before the next A, and B has the same rule. With only two kinds of task, the CPU has to idle twice.
Example 2:
Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 Explanation: With no cooldown, any order works, for example A A A B B B, and no unit is idle.
Example 3:
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 Output: 16 Explanation: One best order is A B C A D E A F G A idle idle A idle idle A. The six A's need two units between each other; the other tasks fill the first gaps, and the CPU idles in the rest.
Constraints:
1 <= tasks.length <= 105- Every task is an uppercase English letter.
0 <= n <= 100
Note:
Your algorithm should run in O(T log 26) time, where T is the number of tasks (log 26 because a heap here never holds more than 26 kinds of task), and use O(1) extra space: at most 26 counts.
The tutorial simulates the CPU with a max-heap: in each unit, run the task with the most copies left, then let it wait in a queue until its cooldown is over. When no task is ready, the time jumps straight to the moment the first waiting task is ready again. (The answer also has a counting shortcut: if the most frequent task appears m times and c tasks appear that often, it is the bigger of tasks.length and (m - 1) · (n + 1) + c.)
Free plan: 30 tutor messages. PRO is unlimited.
