You're given a list of tasks to run on a single CPU and a cooldown rule: after a task runs, the same task can't run again until at least cooldown other time units have passed. Each task takes exactly one unit of time. In any unit the CPU may run a different task or simply sit idle. Your job is to return the minimum number of time units — counting idles — needed to finish every task. This is the classic Task Scheduler problem; the inputs are task identifiers (often single characters) and a cooldown count.
// tasks: string[] — task identifiers, e.g. ['A', 'A', 'A', 'B', 'B', 'B'].
// Repeats are allowed; that's the whole point.
// cooldown: number — minimum number of intervals between two runs of the
// SAME task. cooldown = 2 means at least two other slots
// (other tasks or idles) must sit between two A's.
// returns: number — the fewest time units, idles included, to run them all.
function taskCoordination(tasks, cooldown): number;// A appears 3×, B appears 3×, cooldown 2.
// One optimal order: A B _ A B _ A B (two forced idles).
taskCoordination(['A', 'A', 'A', 'B', 'B', 'B'], 2);
// → 8// Only one task, repeated, with cooldown 2.
// Nothing else can fill the gaps, so the CPU idles: A _ _ A _ _ A.
taskCoordination(['A', 'A', 'A'], 2);
// → 7cooldown = 0 means no gap at all. With no cooldown the tasks just run back-to-back, so the answer is exactly tasks.length.You'll return the fewest time units needed to run a list of tasks on one CPU, given that two runs of the same task must be separated by a fixed cooldown.
Picture a single oven and a stack of trays to bake. After you bake a tray of cookies, that same recipe can't go back in until the oven has cooled for cooldown slots — but you're free to bake something else in the meantime, or leave the oven empty. You want every tray baked in as little wall-clock time as possible. The tricky part is the empty slots: when one recipe dominates the stack and there's nothing else to bake during its cooldown, the oven just sits there, and that wasted time counts. The question is how much total time — baking plus idling — you need.
The surprise is that you never have to plan the actual schedule. Once you know how many times each task appears, a single formula gives the answer.
The task that appears the most often is the bottleneck — it's the one whose cooldowns you can't avoid. Call its count maxFreq. Every other task is just filler: stuff you slot into the gaps the busiest task forces open. So the answer depends almost entirely on maxFreq and on how many tasks tie for that top frequency — not on the order the tasks arrive in, and not on the less-frequent tasks except as gap-fillers.
The natural instinct is to simulate the clock. Walk one time unit at a time. At each tick, pick the available task with the most remaining copies (a task is "available" only if its last run was more than cooldown ticks ago); if nothing is available, idle. Repeat until every task is placed, counting every tick including idles.
function taskCoordinationSim(tasks, cooldown) {
const remaining = new Map();
for (const t of tasks) remaining.set(t, (remaining.get(t) ?? 0) + 1);
const readyAt = new Map(); // task -> earliest tick it may run again
let placed = 0;
let time = 0;
while (placed < tasks.length) {
time += 1;
// Among tasks with copies left AND off cooldown, pick the most frequent.
let best = null;
for (const [task, count] of remaining) {
if (count > 0 && time >= (readyAt.get(task) ?? 0)) {
if (best === null || count > remaining.get(best)) best = task;
}
}
if (best !== null) {
remaining.set(best, remaining.get(best) - 1);
readyAt.set(best, time + cooldown + 1);
placed += 1;
}
// else: this tick is an idle — time still advanced.
}
return time;
}This is correct — the greedy "always run the most frequent ready task" really does produce an optimal schedule. But it earns its answer the hard way. It steps through every time unit, idles included, so for an input like one task repeated a thousand times with a large cooldown, it loops through a thousand baking slots plus all the empty ones in between. The work scales with the answer, not with the input. And the inner scan to find the best ready task adds more cost on top. We can do better: we don't actually need the schedule, only its length.
function taskCoordination(tasks, cooldown) {
if (tasks.length === 0) return 0;
// Count how many times each task appears.
const counts = new Map();
for (const task of tasks) {
counts.set(task, (counts.get(task) ?? 0) + 1);
}
// The busiest task dictates the skeleton.
let maxFreq = 0;
for (const count of counts.values()) {
if (count > maxFreq) maxFreq = count;
}
// How many tasks share that top frequency? They all need a slot in the last row.
let maxCount = 0;
for (const count of counts.values()) {
if (count === maxFreq) maxCount += 1;
}
// (maxFreq - 1) full frames of width (cooldown + 1), plus the final row of
// the maxCount tasks that hit the top frequency. If there are enough distinct
// tasks to fill every idle slot, no idling is needed and the floor is just
// the number of tasks.
const framed = (maxFreq - 1) * (cooldown + 1) + maxCount;
return Math.max(tasks.length, framed);
}
module.exports = { taskCoordination };The whole thing is one counting pass plus a formula. Here's why the formula is what it is.
Lay out the busiest task — the one with maxFreq copies — first. Between every two of its runs you must leave cooldown slots, so you naturally get frames of width cooldown + 1: one slot for the busiest task, then cooldown slots of room. There are maxFreq runs of the busiest task, which means maxFreq - 1 complete frames (the gaps between consecutive runs), and then a final partial frame holding just the last run. That's where (maxFreq - 1) * (cooldown + 1) comes from: the width of all the complete frames.
The + maxCount is the final row. If only one task hits the top frequency, the last frame holds just that one task, so you add 1. But if several tasks tie for maxFreq, each of them needs a slot in that final row — you can't cool any of them down past the end — so you add one slot per tied task. That's maxCount.
And Math.max(tasks.length, …) is the escape hatch. The frame count assumes the gaps need idling. But if you have plenty of other tasks, they pour into those gaps and fill them completely — at which point there are no idles at all, and the schedule is just every task packed end to end, taking exactly tasks.length. Whenever the filler is abundant enough to saturate the gaps, tasks.length is the larger number and wins; whenever the busiest task is so dominant that gaps remain, the frame formula is larger and wins. Taking the max picks the right one automatically.
Trace taskCoordination(['A', 'A', 'A', 'B', 'B', 'B'], 2).
First, count: A → 3, B → 3. So counts = { A: 3, B: 3 }.
Next, find maxFreq. Both counts are 3, so maxFreq = 3.
Then maxCount — how many tasks have a count equal to 3? Both A and B do, so maxCount = 2.
Now plug in. Frame width is cooldown + 1 = 3. There are maxFreq - 1 = 2 complete frames, contributing 2 * 3 = 6 slots. Add the final row of maxCount = 2:
framed = (3 - 1) * (2 + 1) + 2
= 2 * 3 + 2
= 6 + 2
= 8
Finally, Math.max(tasks.length, framed) = Math.max(6, 8) = 8. The formula wins because the busiest task forces real idle gaps. You can read the schedule straight off the frames: A B _ A B _ A B — two frames of A B _, then the final A B. Eight slots, two of them idle, which is exactly what the formula reported without ever placing a single tile.
Now contrast taskCoordination(['A', 'A', 'B', 'C', 'D', 'E'], 1). Counts: A → 2, and B, C, D, E → 1 each. maxFreq = 2, maxCount = 1. Frame width is 2, so framed = (2 - 1) * 2 + 1 = 3. But tasks.length = 6, and Math.max(6, 3) = 6 — there are four other tasks to pour into A's single gap, so nothing idles and the answer is just the task count.
tasks.length floor. The frame formula alone underestimates whenever there are lots of distinct tasks. For ['A','A','B','C','D','E'] with cooldown=1, the formula gives 3, but you obviously can't run six tasks in three units. Math.max(tasks.length, framed) is not optional — drop it and any input with abundant filler returns a number smaller than the task count.cooldown other slots, so the repeating frame is cooldown + 1 wide (the task itself plus its cooldown), not cooldown. Using (maxFreq - 1) * cooldown drops one slot per frame and undercounts every idle-bound case.maxFreq frames instead of maxFreq - 1. There are maxFreq runs of the busiest task but only maxFreq - 1 gaps between them — fenceposts. The last run has no trailing cooldown because the schedule ends. Using maxFreq full frames adds a phantom cooldown after the final task and overcounts by cooldown + 1.maxCount). With ['A','A','A','B','B','B'] and cooldown=2, both A and B hit frequency 3. If you add only 1 for the final row instead of 2, you get 7 and miss the B that must sit in the last row beside the final A. Always count how many tasks share maxFreq, not just that there is a maximum.cooldown = 0. You don't need a branch for it. With cooldown = 0, frame width is 1, so framed = (maxFreq - 1) * 1 + maxCount, which never exceeds tasks.length — the Math.max returns tasks.length on its own. Adding an explicit if (cooldown === 0) is dead code.O(total_time · log k) for k distinct tasks, versus the formula's O(n) count.answer - tasks.length — the slots the formula added beyond the real tasks. It's zero exactly when filler saturates the gaps.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given a list of tasks to run on a single CPU and a cooldown rule: after a task runs, the same task can't run again until at least cooldown other time units have passed. Each task takes exactly one unit of time. In any unit the CPU may run a different task or simply sit idle. Your job is to return the minimum number of time units — counting idles — needed to finish every task. This is the classic Task Scheduler problem; the inputs are task identifiers (often single characters) and a cooldown count.
// tasks: string[] — task identifiers, e.g. ['A', 'A', 'A', 'B', 'B', 'B'].
// Repeats are allowed; that's the whole point.
// cooldown: number — minimum number of intervals between two runs of the
// SAME task. cooldown = 2 means at least two other slots
// (other tasks or idles) must sit between two A's.
// returns: number — the fewest time units, idles included, to run them all.
function taskCoordination(tasks, cooldown): number;// A appears 3×, B appears 3×, cooldown 2.
// One optimal order: A B _ A B _ A B (two forced idles).
taskCoordination(['A', 'A', 'A', 'B', 'B', 'B'], 2);
// → 8// Only one task, repeated, with cooldown 2.
// Nothing else can fill the gaps, so the CPU idles: A _ _ A _ _ A.
taskCoordination(['A', 'A', 'A'], 2);
// → 7cooldown = 0 means no gap at all. With no cooldown the tasks just run back-to-back, so the answer is exactly tasks.length.You'll return the fewest time units needed to run a list of tasks on one CPU, given that two runs of the same task must be separated by a fixed cooldown.
Picture a single oven and a stack of trays to bake. After you bake a tray of cookies, that same recipe can't go back in until the oven has cooled for cooldown slots — but you're free to bake something else in the meantime, or leave the oven empty. You want every tray baked in as little wall-clock time as possible. The tricky part is the empty slots: when one recipe dominates the stack and there's nothing else to bake during its cooldown, the oven just sits there, and that wasted time counts. The question is how much total time — baking plus idling — you need.
The surprise is that you never have to plan the actual schedule. Once you know how many times each task appears, a single formula gives the answer.
The task that appears the most often is the bottleneck — it's the one whose cooldowns you can't avoid. Call its count maxFreq. Every other task is just filler: stuff you slot into the gaps the busiest task forces open. So the answer depends almost entirely on maxFreq and on how many tasks tie for that top frequency — not on the order the tasks arrive in, and not on the less-frequent tasks except as gap-fillers.
The natural instinct is to simulate the clock. Walk one time unit at a time. At each tick, pick the available task with the most remaining copies (a task is "available" only if its last run was more than cooldown ticks ago); if nothing is available, idle. Repeat until every task is placed, counting every tick including idles.
function taskCoordinationSim(tasks, cooldown) {
const remaining = new Map();
for (const t of tasks) remaining.set(t, (remaining.get(t) ?? 0) + 1);
const readyAt = new Map(); // task -> earliest tick it may run again
let placed = 0;
let time = 0;
while (placed < tasks.length) {
time += 1;
// Among tasks with copies left AND off cooldown, pick the most frequent.
let best = null;
for (const [task, count] of remaining) {
if (count > 0 && time >= (readyAt.get(task) ?? 0)) {
if (best === null || count > remaining.get(best)) best = task;
}
}
if (best !== null) {
remaining.set(best, remaining.get(best) - 1);
readyAt.set(best, time + cooldown + 1);
placed += 1;
}
// else: this tick is an idle — time still advanced.
}
return time;
}This is correct — the greedy "always run the most frequent ready task" really does produce an optimal schedule. But it earns its answer the hard way. It steps through every time unit, idles included, so for an input like one task repeated a thousand times with a large cooldown, it loops through a thousand baking slots plus all the empty ones in between. The work scales with the answer, not with the input. And the inner scan to find the best ready task adds more cost on top. We can do better: we don't actually need the schedule, only its length.
function taskCoordination(tasks, cooldown) {
if (tasks.length === 0) return 0;
// Count how many times each task appears.
const counts = new Map();
for (const task of tasks) {
counts.set(task, (counts.get(task) ?? 0) + 1);
}
// The busiest task dictates the skeleton.
let maxFreq = 0;
for (const count of counts.values()) {
if (count > maxFreq) maxFreq = count;
}
// How many tasks share that top frequency? They all need a slot in the last row.
let maxCount = 0;
for (const count of counts.values()) {
if (count === maxFreq) maxCount += 1;
}
// (maxFreq - 1) full frames of width (cooldown + 1), plus the final row of
// the maxCount tasks that hit the top frequency. If there are enough distinct
// tasks to fill every idle slot, no idling is needed and the floor is just
// the number of tasks.
const framed = (maxFreq - 1) * (cooldown + 1) + maxCount;
return Math.max(tasks.length, framed);
}
module.exports = { taskCoordination };The whole thing is one counting pass plus a formula. Here's why the formula is what it is.
Lay out the busiest task — the one with maxFreq copies — first. Between every two of its runs you must leave cooldown slots, so you naturally get frames of width cooldown + 1: one slot for the busiest task, then cooldown slots of room. There are maxFreq runs of the busiest task, which means maxFreq - 1 complete frames (the gaps between consecutive runs), and then a final partial frame holding just the last run. That's where (maxFreq - 1) * (cooldown + 1) comes from: the width of all the complete frames.
The + maxCount is the final row. If only one task hits the top frequency, the last frame holds just that one task, so you add 1. But if several tasks tie for maxFreq, each of them needs a slot in that final row — you can't cool any of them down past the end — so you add one slot per tied task. That's maxCount.
And Math.max(tasks.length, …) is the escape hatch. The frame count assumes the gaps need idling. But if you have plenty of other tasks, they pour into those gaps and fill them completely — at which point there are no idles at all, and the schedule is just every task packed end to end, taking exactly tasks.length. Whenever the filler is abundant enough to saturate the gaps, tasks.length is the larger number and wins; whenever the busiest task is so dominant that gaps remain, the frame formula is larger and wins. Taking the max picks the right one automatically.
Trace taskCoordination(['A', 'A', 'A', 'B', 'B', 'B'], 2).
First, count: A → 3, B → 3. So counts = { A: 3, B: 3 }.
Next, find maxFreq. Both counts are 3, so maxFreq = 3.
Then maxCount — how many tasks have a count equal to 3? Both A and B do, so maxCount = 2.
Now plug in. Frame width is cooldown + 1 = 3. There are maxFreq - 1 = 2 complete frames, contributing 2 * 3 = 6 slots. Add the final row of maxCount = 2:
framed = (3 - 1) * (2 + 1) + 2
= 2 * 3 + 2
= 6 + 2
= 8
Finally, Math.max(tasks.length, framed) = Math.max(6, 8) = 8. The formula wins because the busiest task forces real idle gaps. You can read the schedule straight off the frames: A B _ A B _ A B — two frames of A B _, then the final A B. Eight slots, two of them idle, which is exactly what the formula reported without ever placing a single tile.
Now contrast taskCoordination(['A', 'A', 'B', 'C', 'D', 'E'], 1). Counts: A → 2, and B, C, D, E → 1 each. maxFreq = 2, maxCount = 1. Frame width is 2, so framed = (2 - 1) * 2 + 1 = 3. But tasks.length = 6, and Math.max(6, 3) = 6 — there are four other tasks to pour into A's single gap, so nothing idles and the answer is just the task count.
tasks.length floor. The frame formula alone underestimates whenever there are lots of distinct tasks. For ['A','A','B','C','D','E'] with cooldown=1, the formula gives 3, but you obviously can't run six tasks in three units. Math.max(tasks.length, framed) is not optional — drop it and any input with abundant filler returns a number smaller than the task count.cooldown other slots, so the repeating frame is cooldown + 1 wide (the task itself plus its cooldown), not cooldown. Using (maxFreq - 1) * cooldown drops one slot per frame and undercounts every idle-bound case.maxFreq frames instead of maxFreq - 1. There are maxFreq runs of the busiest task but only maxFreq - 1 gaps between them — fenceposts. The last run has no trailing cooldown because the schedule ends. Using maxFreq full frames adds a phantom cooldown after the final task and overcounts by cooldown + 1.maxCount). With ['A','A','A','B','B','B'] and cooldown=2, both A and B hit frequency 3. If you add only 1 for the final row instead of 2, you get 7 and miss the B that must sit in the last row beside the final A. Always count how many tasks share maxFreq, not just that there is a maximum.cooldown = 0. You don't need a branch for it. With cooldown = 0, frame width is 1, so framed = (maxFreq - 1) * 1 + maxCount, which never exceeds tasks.length — the Math.max returns tasks.length on its own. Adding an explicit if (cooldown === 0) is dead code.O(total_time · log k) for k distinct tasks, versus the formula's O(n) count.answer - tasks.length — the slots the formula added beyond the real tasks. It's zero exactly when filler saturates the gaps.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.