All problems

Task Scheduler

Medium · greedy

A processor runs one task in each time slot. You are given tasks, a string of capital letters where each letter is one task, and the same letter means the same kind of task. The tasks can be done in any order, and a slot may also be left idle, doing nothing.

After a kind of task runs, the processor needs a rest from that kind: between any two tasks of the same letter there must be at least cooldown slots in which something else runs, or which are idle. Different letters never affect each other.

Return the smallest total number of slots needed to run every task, counting idle slots.

Examples

Example 1

Input: tasks = "AAABBB", cooldown = 2

Output: 8

One schedule is A B idle A B idle A B. Each A is followed by two slots before the next A, and the same for B.

Example 2

Input: tasks = "AAABBB", cooldown = 0

Output: 6

With no rest needed, the six tasks run back to back in six slots.

Example 3

Input: tasks = "AAAABC", cooldown = 2

Output: 10

The four A tasks need two slots between each pair. B and C fill two of the gaps, and the other four gap slots stay idle: A B C A idle idle A idle idle A.

Constraints

• 1 <= len(tasks) <= 10^4
• tasks contains only capital letters A to Z
• 0 <= cooldown <= 10^4