The problem
With starting capital w, pick at most k projects (each has a capital requirement and a profit; profit adds to capital permanently) to maximize final capital.
Stuck? Reveal hints one at a time
How to approach it
- 1Sort projects ascending by required capital.
- 2Repeat up to k times: move every project whose requirement ≤ current capital into a profit max-heap.
- 3Pop the max profit and add it to capital. If the heap is empty, stop early — nothing is affordable.
- 4Return the final capital.
Key insight
Capital only grows, so the "affordable" frontier only advances — each project is transferred into the heap exactly once, making the whole loop O(n log n) not O(k·n).
The solution
Watch out for
- Break when nothing is affordable — looping k times regardless wastes time and can misread the greedy.
- Profits do not reduce capital; requirements are thresholds, not costs.