IPO
hardTime: O(n log n)Space: O(n)
Recognize the pattern
maximize capital after k investmentstwo heaps: affordable and profitablegreedy selection
Brute force idea
Try all combinations — O(C(n,k)).
Better approach
Min-heap by capital, max-heap by profit. Each round: move newly affordable projects to profit heap, pick most profitable. O(n log n).
Key invariant
As capital grows, more projects become affordable. The profit heap always picks the best available option.
Watch out for
Not pre-sorting by capital — the min-heap feeds the profit heap efficiently as budget increases.