Task Scheduler

Medium

Problem

Tasks are letters, and each takes one unit of time. Two runs of the same task must be at least n units apart; the CPU can idle in between. Return the minimum total time to finish all tasks.

Example 1

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

A B idle A B idle A B.

Example 2

Input:  same tasks, n = 0
Output: 6

Test cases

Case 1

Input:    ["A","A","A","B","B","B"], 2
Expected: 8

Case 2

Input:    ["A","A","A","B","B","B"], 0
Expected: 6

Case 3

Input:    ["A","A","A","A","A","A","B","C","D","E","F","G"], 2
Expected: 16

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Counting formula

Time O(n)Space O(26)

The most frequent task (count f) forces (f − 1) blocks of length n + 1, plus one slot for each task tied at count f. If tasks outnumber that, no idle is needed.

function leastInterval(tasks, n) {
const cnt = new Array(26).fill(0);
for (const t of tasks) cnt[t.charCodeAt(0) - 65]++;
const f = Math.max(...cnt);
const tied = cnt.filter((c) => c === f).length;
return Math.max(tasks.length, (f - 1) * (n + 1) + tied);
}

The simulation (max-heap of counts + cooldown queue) is O(total time) and easier to derive live — present it if the formula does not come to you.