Pattern visualizer

IPO (Maximize Capital)

Capital only ever grows, so a project affordable now stays affordable forever — nothing you skip becomes ineligible later. That monotonicity means the right move each round is simply the highest-profit project among everything currently affordable. Sorting projects by capital once, then sliding a pointer forward as w grows, feeds a max-heap (keyed on profit) exactly the newly-unlocked candidates — never re-scanning ones already inside it. Animated on: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] — invest in at most k projects, each needing its listed capital up front, to maximize final capital. Expected: 4..

Two heaps: capital-gate, then greedy max-profit

time O(n log n)space O(n)step 1 / 8

line 6

Sorted by capital: A(cap 0, profit 1), B(cap 1, profit 2), C(cap 1, profit 3). Project A's capital 0 <= w(0), so push its profit 1 onto the max-heap.

Pseudocode

1FUNCTION maxCapital(k, w, profits, capital):
2  SORT projects BY capital ascending
3  i <- 0
4  FOR round <- 1 TO k:
5    WHILE i < LENGTH(projects) AND projects[i].capital <= w:
6      INSERT(maxHeap, projects[i].profit)
7      i <- i + 1
8    IF maxHeap IS EMPTY: BREAK
9    w <- w + EXTRACT-MAX(maxHeap)
10  RETURN w

← / → step · space play · Home restart

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap