LeetCode 621 Greedy + Max-Heap Medium

Task Scheduler — Greedy + Heap

Always run the most frequent ready task. A max-heap picks it; a cooldown queue holds tasks until they're allowed back — O(N log 26) time

The greedy choice

Identical tasks must be separated by at least n cooldown slots. The greedy insight: at every tick, run the task with the most remaining copies. Starve the bottleneck task and you'll be forced into idle time later, so tackle the busiest one first, always.

A max-heap keyed on remaining count gives you that pick in O(log 26). After running a task, it can't return immediately: park it in a cooldown queue with the time it becomes available again. Each tick, release anything whose cooldown has expired back into the heap.

// each time tick
time += 1
if heap: run most-frequent task
  if count-1 > 0:
    cooldown.push(task, time+n)
else: idle
release expired from cooldown → heap
LC
Task Scheduler (621): a clean greedy-plus-heap simulation. There's also a slick O(N) formula, but the heap version generalizes and shows why the greedy works.
Open Problem
Time Complexity
O(T log 26)

T = total ticks (answer length). Each tick does O(log 26) heap work; at most 26 distinct task types.

Space Complexity
O(26)

Heap and cooldown queue together hold at most 26 task types.

Live Visualization
Ready in heap Ran this tick Cooling down Idle
Ready queue max-heap by remaining count
Cooldown queue (task · available-at time)
Timeline (each slot = one time unit)
time = 0 ran = – heap size = 0 idles = 0
Step 0 / 0
Time elapsed
0
total ticks
Ran this tick
–
most frequent
Idle slots
0
forced gaps
Tasks left
0
not yet run
Set tasks and cooldown n, then hit Play to watch the greedy scheduler run.
✓ Done Speed

Step-by-step trace

#TimeActionRanHeap (count)CoolingIdles
C++ — Task Scheduler (LC 621), heap simulation 
int leastInterval(vector<char>& tasks, int n) {
    vector<int> freq(26, 0);
    for (char t : tasks) freq[t - 'A']++;

    priority_queue<int> pq;              // max-heap of remaining counts
    for (int f : freq) if (f) pq.push(f);

    int time = 0;
    queue<pair<int,int>> cool;      // {remaining, availableAt}

    while (!pq.empty() || !cool.empty()) {
        time++;
        if (!pq.empty()) {
            int rem = pq.top() - 1;  pq.pop();  // run most frequent
            if (rem > 0) cool.push({rem, time + n});
        }
        // release a task whose cooldown just expired
        if (!cool.empty() && cool.front().second == time)  {
            pq.push(cool.front().first);
            cool.pop();
        }
    }
    return time;
}

📝 My Notes ●

▾
Saved 0 chars