Task Scheduler

The key idea

The most frequent task dictates the schedule. Lay its copies out as a skeleton with n gaps between them, then fill the gaps with other tasks; any unfilled gap becomes idle. The answer is max(len(tasks), (maxFreq - 1) * (n + 1) + countOfMax).

Problem

You are given an array of CPU tasks, each represented by an uppercase letter, and a non-negative integer n. Each task takes one unit of time, and the CPU does exactly one task (or stays idle) per unit. The only rule is a cooldown: two runs of the same task must be separated by at least n units of time, during which the CPU may run different tasks or sit idle. Return the minimum number of units of time the CPU needs to finish all the given tasks.

Constraints

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

Examples

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8

Input: tasks = ["A","C","A","B","D","B"], n = 1 Output: 6

Input: tasks = ["A","A","A","B","B","B"], n = 3 Output: 10

Complexity

Time: O(N) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →