Task Scheduler

medium

You are given an array of CPU tasks, each represented by a letter A-Z, and a cooling interval n. You can perform the tasks in any order, but between two same tasks there must be at least n units of time (during which other tasks can run, or the CPU idles).

Return the least number of units of time the CPU will take to finish all the given tasks.

Test Cases

Copy an input into the main harness and Run to verify

Input

tasks = ["A","A","A","B","B","B"], n = 2

Expected Output

8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B. There is at least 2 units of time between any two same tasks.

Input

tasks = ["A","C","A","B","D","B"], n = 1

Expected Output

6

Input

tasks = ["A","A","A","B","B","B"], n = 3

Expected Output

10

Constraints

1 <= tasks.length <= 10^4
tasks[i] is an uppercase English letter.
0 <= n <= 100

Hints

Hint 1 — click to reveal

The bottleneck is the most frequent task.

Hint 2 — click to reveal

Think in frames of size (n + 1): how many full frames, and who fills the last frame?

Java Compiler