Task Scheduler

We’re given a character array, tasks, where each character represents a unique task. These tasks need to be performed by a single CPU, with each task taking one unit of time. The tasks can be performed in any order. At any given time, a CPU can either perform some task or stay idle. For the given tasks, we are also provided with a positive integer value, n, which represents the cooling period between any two identical tasks. This means that the CPU must wait for at least n units of time before it performs the same task again. For example, if we have the tasks [ A , B , A , C ] [A,B,A,C] and n = 2, then after performing the first A A task, the CPU will wait for at least 2 units of time to perform the second A A task. During these 2 units of time, the CPU can either perform some other task or stay idle. Given the two input values, tasks and n, find the least number of units of time the CPU will take to perform the given tasks.

Constraints

• 1 ≤ tasks.length ≤ 1000
• tasks consists of uppercase English letters.
• 0 ≤ n ≤ 100

Examples

Let's take a look at a few examples to get a better understanding of the problem statement:

Example 1

Input:

• Tasks: A, A, B, B
• n = 2

Schedule: A, B, Idle, A, B

Explanation: We scheduled tasks A and B in this manner to get to the minimum number of units of time.

Output: Units of time = 5

Example 2

Input:

• Tasks: A, A, A, B, B, C, C
• n = 3

Schedule: A, B, C, A, Idle, B, Idle, Idle, A

Explanation: We first scheduled all the A tasks, then all the B tasks, and lastly all of the C tasks to get to the minimum number of units of time.

Output: Units of time = 9

Example 3

Input:

• Tasks: A, A, B, C
• n = 0

Schedule: B, A, C, A

Note: Here, we can have any permutation of size 4 since n = 0. For example: [A, B, C, A], [A, B, A, C], [B, C, A, A], [C, B, A, A], [A, A, C, B].

Explanation: As n = 0, it will have zero effect on CPU's processing time. Therefore, we can schedule the tasks in any way we want.

Output: Units of time = 4