Mediumgreedy
Task Scheduler
Problem (restated)
CPU tasks labeled A-Z. Same letter needs cooldown n between runs. Any order; idle allowed. Min total units of time.
Intuition
Most frequent task forces (maxf-1) gaps of length n. Fill gaps with other tasks; leftover idles pad the schedule.
Approaches
Idle slots from max frequency
Tested onlyTime O(n)Space O(1)
Idea. idles = max(0, empty, available); answer = tasks + idles. Multiple max-freq tasks shrink gap width.
Walkthrough. tasks=AAABBB, n=2 → 8.
Trade-offs. Priority queue simulation is O(n log 26); formula is O(n).
Solution
export function leastInterval(tasks: string[], n: number): number {
const freq = Array(26).fill(0);
let maxf = 0, maxCount = 0;
for (const t of tasks) {
const i = t.charCodeAt(0) - 65;
freq[i]!++;
if (freq[i]! > maxf) {
maxf = freq[i]!;
maxCount = 1;
} else if (freq[i] === maxf) maxCount++;
}
const parts = maxf - 1;
const partLen = n - (maxCount - 1);
const empty = Math.max(0, parts * partLen);
const available = tasks.length - maxf * maxCount;
const idles = Math.max(0, empty - available);
return tasks.length + idles;
}
export function leastInterval(tasks: string[], n: number): number {
const freq = Array(26).fill(0);
let maxf = 0, maxCount = 0;
for (const t of tasks) {
const i = t.charCodeAt(0) - 65;
freq[i]!++;
if (freq[i]! > maxf) {
maxf = freq[i]!;
maxCount = 1;
} else if (freq[i] === maxf) maxCount++;
}
const parts = maxf - 1;
const partLen = n - (maxCount - 1);
const empty = Math.max(0, parts * partLen);
const available = tasks.length - maxf * maxCount;
const idles = Math.max(0, empty - available);
return tasks.length + idles;
}
Template connection
Greedy packing / frequency bottleneck.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?