Greedy, Heaps, And Scheduling Optimization

What's being tested

These problems test greedy choice, priority-queue invariants, and efficient array reasoning under ordering constraints. Interviewers are probing whether you can replace brute-force scans or pairings with O(n log n) or O(n) structures, justify correctness, and handle duplicates, empty inputs, and boundary cases cleanly.

Patterns & templates

• Monotonic stack for nearest-smaller relationships — O(n) time, O(n) space; decide strict < versus <= before coding duplicates.

• Fenwick tree or segment tree for rightmost-smaller queries — coordinate-compress values, store max index, query values < a[i] in O(log n).

• Two heaps for streaming median — max-heap lower half, min-heap upper half; rebalance after every addNum() to keep sizes within one.

• Greedy resource allocation — sort counts/capacities, consume smallest feasible requirement first; prove exchange argument, not just “seems optimal.”

• Heap scheduling template — sort events by start time, push active candidates into heapq, pop expired or highest-priority item; usually O(n log n).

• Pairing optimization — sort both sides or sort by constraint then use a heap; watch whether objective is max sum, min operations, or feasibility.

• Range-update minimization — reason on adjacent differences, not full arrays; difference arrays often turn repeated interval operations into linear accounting.

Common pitfalls

Pitfall: Treating “nearest smaller” and “rightmost smaller” as the same problem; the former is usually stack-based, the latter often needs indexed value queries.

Pitfall: Using Python heapq as a max-heap without negating priorities, or forgetting tie-breaking when equal priorities affect deterministic output.

Pitfall: Giving a greedy algorithm without a correctness argument; state the invariant or exchange proof before moving to implementation details.

Practice these

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