Hints — p88 IPO

  1. Greedy: at every round, pick the max-profit affordable project. Exchange-argument proves optimality.

  2. Two heaps: min-heap-by-capital = waiting room of unaffordable projects; max-heap-by-profit = pool of affordable projects.

  3. Each round: drain min-heap into max-heap while top capital ≤ current w. Pop max-profit; add to w. Break if max-heap empty (nothing affordable).

  4. Alternative (simpler): sort projects by capital ascending. Walk a pointer through sorted list; push profit to max-heap whenever capital[ptr] ≤ w.

  5. Both run in O((n + k) log n). Each project is promoted at most once.

If stuck: see solution.py.