-
Notifications
You must be signed in to change notification settings - Fork 0
098 — Task Scheduler
LeetCode 621 · Medium. Given an array tasks of characters (each representing a task type) and a non-negative integer n — the required cooldown between two executions of the same task type — return the minimum number of time units (including idle units) needed to complete all tasks. At each unit of time, the CPU can either run one task or sit idle.
Picture a chef with several dishes cooking at once, each needing to rest for n minutes between stirs. At every free minute, the chef's best move is obvious: stir whichever dish currently has the most stirring left to do (it's the one most likely to become a bottleneck later), as long as it isn't still resting. If nothing is ready to be stirred, the chef has no choice but to stand around — an idle tick. Repeating "stir whatever's most in-demand and currently available" until every dish is fully done is exactly the greedy strategy that solves this problem, and "most in-demand" is a question a max-heap answers instantly.
"Schedule tasks with a cooldown, minimize total time, always run the task that's most urgent right now" — any time a problem needs a repeated "which of my currently-available options is best?" query, where the pool of options shrinks and changes after every step, that's a max-heap driving a greedy simulation.
Track each task type's remaining count and the earliest time it's allowed to run again. At every tick, linearly scan all task types for the one with the highest remaining count that's currently off cooldown, run it, and advance time — one unit at a time, whether a task runs or the CPU idles.
func leastIntervalBruteForce(_ tasks: [Character], _ n: Int) -> Int {
var counts = [Character: Int]()
for task in tasks {
counts[task, default: 0] += 1
}
var nextAvailable = [Character: Int]()
var remaining = tasks.count
var time = 0
while remaining > 0 {
var bestTask: Character? = nil
var bestCount = 0
// scan every task type currently off cooldown, pick the one with the most left to do
for (task, count) in counts where count > 0 && (nextAvailable[task] ?? 0) <= time {
if count > bestCount {
bestCount = count
bestTask = task
}
}
if let task = bestTask {
counts[task]! -= 1
nextAvailable[task] = time + n + 1
remaining -= 1
}
time += 1
}
return time
}
// smoke test
print(leastIntervalBruteForce(Array("AAABBB"), 2)) // 8
print(leastIntervalBruteForce(Array("AAABBB"), 0)) // 6 — no cooldown, no idling needed
print(leastIntervalBruteForce(Array("A"), 2)) // 1 — a single task, run once
print(leastIntervalBruteForce(Array("AAAAAABCDEFG"), 2)) // 16Big-O: each of the O(time) ticks scans up to 26 task types looking for the current best, so this runs in O(time · 26), where time is the length of the final schedule. Since the alphabet size (26) is a constant, this is effectively O(time) here — but the approach itself, a full linear scan every tick, wouldn't scale if the number of distinct task types weren't capped at 26.
Push every task type's remaining count into a max-heap up front. Each tick, pop the currently-highest count, run it once, and — if it still has work left — place it in a cooldown queue tagged with the tick it becomes available again. Whenever the front of that cooldown queue becomes ready, push it back onto the heap.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
var counts = [Character: Int]()
for task in tasks {
counts[task, default: 0] += 1
}
var heap = Heap<Int>(sort: >) // max-heap of remaining counts, by task count only — identity doesn't matter
for count in counts.values {
heap.insert(count)
}
var time = 0
var cooldownQueue: [(count: Int, readyAt: Int)] = [] // tasks currently cooling down, in ready-time order
while !heap.isEmpty || !cooldownQueue.isEmpty {
time += 1
if let count = heap.extract() {
let remaining = count - 1
if remaining > 0 {
cooldownQueue.append((remaining, time + n))
}
}
// else: heap was empty this tick — an idle unit, nothing to run
// the queue's ready times only ever increase, so checking just the front is enough
if let front = cooldownQueue.first, front.readyAt == time {
heap.insert(front.count)
cooldownQueue.removeFirst()
}
}
return time
}
// smoke test — same cases as the brute force
print(leastInterval(Array("AAABBB"), 2)) // 8
print(leastInterval(Array("AAABBB"), 0)) // 6
print(leastInterval(Array("A"), 2)) // 1
print(leastInterval(Array("AAAAAABCDEFG"), 2)) // 16Big-O: with m distinct task types (m ≤ 26), building the heap is O(m), and each of the O(time) ticks does at most one O(log m) heap operation, for O(time · log m) overall. Because m is capped at 26 in this problem, that's asymptotically close to the brute force's O(time · 26) — the real payoff of the heap-based approach is that it generalizes cleanly to problems where the number of distinct categories isn't small and fixed, at which point log m beats a full linear scan outright.
Both approaches implement the same greedy idea — always run whichever available task type currently has the most work left — but they differ in how they find "currently has the most work left." The brute force re-derives that answer from scratch every tick by scanning every task type. The heap-based approach instead maintains that answer continuously: a max-heap's root is always the current leader, so finding it costs nothing beyond a peek, and only the act of changing the leaderboard (removing the one that just ran, re-adding it once its cooldown expires) costs anything, at O(log m). That's the general heap payoff — cheap incremental updates instead of full recomputation — even though, for this specific problem's small fixed alphabet, the constant-factor win is modest.
- Heaps and Priority Queues — the max-heap of remaining counts driving the simulation above.
- Top K and Heap Pattern — "always grab the current largest" is this pattern's core move, applied here once per tick rather than once total.
- Greedy — "always schedule the currently most-needed task" is a greedy choice, and it's provably optimal for minimizing total schedule length in this problem.
Task Scheduler is a chef stirring whatever dish is most in-demand and off cooldown — a max-heap always knows who's most in-demand, and a queue tracks who's still resting.
- Why does the
cooldownQueueonly ever need to check its front element for readiness, rather than scanning the whole queue every tick? - Trace
leastInterval(Array("A"), 2)by hand. Why does the loop terminate after just one tick even thoughn = 2? - The
Heap<Int>in the optimal solution stores plain counts, with no record of which task type each count belongs to. Explain why the algorithm still produces the correct minimum time despite "losing" that identity information. - What would break (or would nothing break?) if the
if let front = cooldownQueue.first, front.readyAt == timecheck used<=instead of==?
⬅️ Previous: Kth Largest Element in an Array · Next: Design Twitter ➡️