Task Scheduler

Medium · Heap / Priority Queue

You are given a list of CPU tasks represented as single letters, and a cooldown number n. Each CPU cycle you can run one task or stay idle, but the same task letter must be separated by at least n cycles from its previous run. Return the minimum total number of cycles needed to finish all the tasks, inserting idle cycles only when unavoidable.

Examples

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Why:    One valid order is A,B,idle,A,B,idle,A,B which takes 8 cycles because A and B each need a 2-cycle gap between repeats.

Input:  tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Why:    With no cooldown required, the six tasks can just run back to back.

Input:  tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Why:    A needs 5 gaps of size 2 after it, and there are enough other distinct tasks to fill most idle slots, giving 16 total cycles.

Constraints

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

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Task Scheduler

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Task Scheduler. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.