Greedy Algorithms And Priority Queues

What's being tested

These problems test greedy choice validation, priority queue design, and stateful data-structure updates under ordering constraints. You need to show why the local choice is safe, choose the right heap/tree/map representation, and handle ties, partial updates, and edge cases deterministically.

Patterns & templates

• Max-heap selection with unlock constraints — sort by requirement, push feasible profits into heapq; each step picks best available in O(n log n).

• Min-heap tree construction — Huffman-style merge by frequency; include deterministic tie-breakers like (freq, symbol_id, node_id) to avoid ambiguous encodings.

• Price-time priority matching — maintain buy/sell books using heaps plus FIFO queues; best price wins, then earliest timestamp, with partial fills preserved.

• Greedy proof template — state invariant, prove exchange argument, then show each chosen item cannot make a better future solution impossible.

• Heap deletion gotcha — heapq lacks efficient arbitrary removal; use lazy deletion, indexed heaps, or balanced maps depending on update/cancel requirements.

• Grid escape with time constraints — model as shortest path/BFS/Dijkstra over (row, col, time); avoid greedy moves unless monotonicity is proven.

• Complexity discipline — aim for O(n log n) for selection/tree/order-book operations; explain when O(n^2) scans will fail.

Common pitfalls

Pitfall: Picking the highest-profit project before checking capital feasibility breaks the greedy invariant; only choose among currently unlocked candidates.

Pitfall: Building a frequency tree without stable tie-breaking can produce correct-looking but non-reproducible encode/decode behavior.

Pitfall: Treating an order book as “sort all orders after every event” is usually too slow; maintain incremental priority structures instead.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.