Scheduling & Greedy with Regret

Many greedy problems need "the best option right now" again and again while the options change. A heap gives you that in $O(\log n)$. This note covers two shapes: scheduling (a heap picks the top task, a queue parks tasks that aren't ready yet) and greedy with regret (commit to a choice now, and use a heap to take back the worst one later).

The idea#

Scheduling problems ask you to pick the best option at each step while some items are not ready yet. Two heap shapes cover most of them.

Heap + waiting queue#

For scheduling and ranking, use a queue for items that can only be processed after a condition, and a heap to process the top item first. For tasks with a cooldown:

1. Pop the most frequent task from a max-heap and run it.
2. If it still has copies left, park it in a FIFO queue with the time it becomes ready again.
3. Before each step, move the front of the queue back into the heap if its ready time has come.

Running the most frequent task first is the greedy choice: it is the task most likely to be left over with nothing to separate its copies. The queue is FIFO because every parked task waits the same cooldown, so the earliest parked is always the earliest ready.

Greedy with regret#

Sometimes you can't tell which choice is best until later. Picture two resources, like the ladders and bricks in Furthest Building You Can Reach: one covers a need of any size per use (so it is worth most on the biggest needs), and one is paid per unit. While walking forward you can't know whether a bigger need is ahead or already behind you.

The fix is to commit now and correct later:

1. Give every need the "any size" resource and record the need in a min-heap.
2. When you have used more of it than you own, take it back from the smallest recorded need and pay for that need per unit instead.
3. When the per-unit budget goes negative, you can't go further.

Why it works: the heap always holds the largest needs seen so far, so the per-unit budget is always spent on the smallest ones. That is exactly the optimal assignment, found in one pass.

How to spot it#

These cues point to a heap-driven greedy.

• Tasks with cooldowns, or "no two equal items adjacent".
• Events sorted by time, where you repeatedly pick the shortest, cheapest or most profitable of those currently available (sort by arrival, heap by priority). The heap might hold processing times, event end days (Maximum Number of Events), or room end times.
• Two kinds of resource where one is "unlimited per use" (ladders, refuels) and should go to the largest needs.
• A DP over (index, resource A, resource B) that is far too big. That often hints at a regret heap.

Template#

Here are both shapes from "The idea" as code. The cooldown shape uses one heap and one queue. A step where the heap is empty but the queue is not means either "no valid order" or "idle", depending on the problem.

heap = max-heap of (remaining count, task)
waiting = empty FIFO queue of (count, task, ready_at)
for each step:
    if front of waiting is ready at this step:
        move it from waiting back onto heap
    if heap is empty:
        fail, or count an idle step         # all left are cooling down
    pop the top task; run it
    if it has copies left:
        append (count - 1, task, step + cooldown + 1) to waiting

The regret shape needs only a min-heap of the needs that currently hold the "any size" resource.

held = empty min-heap                    # smallest held need on top
for each need, moving forward:
    if need <= 0: continue
    push need onto held                  # give it the resource for now
    if len(held) > resource count:
        budget -= pop smallest from held # regret: pay per unit instead
        if budget < 0: stop here

Both run in $O(n \log k)$, where $k$ is the heap size (the alphabet, or the resource count).

Pitfalls#

Watch for these when you adapt the templates.

• Empty heap, non-empty queue. Decide what it means for your problem: no valid order, or an idle step.
• Wrong ready time. A task run at step t with cooldown n is ready again at t + n + 1, not t + n.
• Reaching for DP first. A memo over (index, resource A, resource B) is often far too large; a regret heap is $O(n \log k)$.
• Using a closed-form formula without its picture. Formulas for cooldown problems hide edge terms that are easy to get wrong. Derive them from a picture of the schedule.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

• 621. Task Scheduler
• 767. Reorganize String
• 1642. Furthest Building You Can Reach
• 1405. Longest Happy String
• 1834. Single-Threaded CPU
• 871. Minimum Number of Refueling Stops
• 1383. Maximum Performance of a Team
• 2402. Meeting Rooms III
• 1851. Minimum Interval to Include Each Query

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• A heap picks the best task now; a FIFO queue holds tasks until their cooldown ends.
• Most frequent first is the greedy choice for cooldown problems.
• Greedy with regret: commit to a choice now and keep it in a heap, so you can undo the worst one later.
• A ladder is worth any number of bricks, so ladders belong on the largest climbs.
• Sort by availability, then heap by priority, for jobs that arrive over time.