Sign in to watch this lesson
Advanced - Greedy and Scheduling · 3:57
Regret Greedy and Heap-Driven Choices
A regret greedy takes the locally best move but leaves a token in a heap, so a later, better option can undo it at its marginal cost. With one share per day and unlimited holdings, a min-heap that pushes each sale's price twice (a regret token and a possible buy) finds the maximum profit. The same heap-as-budget pattern solves Furthest Building, Refueling Stops and IPO, and Huffman merging (always merge the two smallest) minimizes total merge cost.
You will learn
- Implement the regret heap for one-trade-per-day buy/sell (min-heap, profit p − min, push p twice after a sale)
- Explain how popping a regret token reroutes an earlier trade (buy 1, sell 2, then 10 becomes buy 1, sell 10)
- Recognise heap-as-budget greedies: ladders (min-heap of size k), refueling (max-heap of passed stations), IPO
- Minimize total merge cost with Huffman merging and justify it with an exchange argument