DSA problem
Task Scheduler
Given a character array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks: there must be at least n units of time between any two same tasks. Return the least number of units of times that the CPU will take to finish all the given tasks.
The interesting structure is that the most frequent task essentially "skeletonizes" the entire schedule. Suppose the most frequent task has frequency f and there are c distinct tasks tied for that frequency. The most-frequent task will appear f times, spaced at least n apart, forming f - 1 gaps of size n + 1 plus one trailing block. The total length contributed by this skeleton is (f - 1) * (n + 1) + c — the trailing block contains all c tasks that share the top frequency.
If we have more "filler" tasks than empty slots in that skeleton, the schedule cannot be compressed any further, and the answer is just the number of tasks len(tasks). Otherwise idle gaps remain and the answer is the skeleton length (f - 1) * (n + 1) + c. The final formula is max(len(tasks), (f - 1) * (n + 1) + c).
This greedy / counting solution runs in O(n) time (a single pass over the tasks to count frequencies, plus a constant-time formula). Space is O(1) because there are at most 26 task types. The proof is a direct construction: pack tasks into the slots of the skeleton in round-robin, longest queue first — a strategy that never violates the cooldown when slots are sufficient.
Examples
tasks = ["A","A","A","B","B","B"], n = 28tasks = ["A","C","A","B","D","B"], n = 16tasks = ["A","A","A","B","B","B"], n = 06Constraints
- 1 <= task.length <= 10^4
- tasks[i] is an uppercase English letter.
- 0 <= n <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.