IPO

You are given k (max number of projects), initial capital w, and arrays profits[i] and capital[i]. Each project requires capital[i] to start and yields profits[i] after completion. Choose up to k projects to maximize final capital.

Why this is worth learning

Feasibility depends on current capital, while desirability depends on profit. Sort once by capital requirement, then use a max-heap to choose the best profit among projects that are currently affordable.

Before coding: one-minute experiment

With w=0, k=2, requirements [0,1,1], and profits [1,2,3], what is selected? Should a negative-profit affordable project ever be required?

Function signature

func FindMaximizedCapital(k int, w int, profits []int, capital []int) int

Inputs / outputs

• k: maximum number of projects.
• w: initial capital.
• profits: profits per project.
• capital: required capital per project.
• Return: maximum capital after at most k projects.

Example

k = 2, w = 0
profits = [1,2,3]
capital = [0,1,1]
Output: 4

Constraints

• 1 <= len(profits) <= 100_000
• len(capital) == len(profits) and k >= 0.
• The maximum final capital is guaranteed to fit the target Go int.

Core idea (near-solution)

Exhaustively enumerating affordable project sequences is a correct small-instance model, including the choice to stop. To reduce it, separate eligibility from reward. Capital requirements decide which projects are available; profits decide which available project leaves the most resources for the future. A larger positive profit cannot remove a later option because requirements are thresholds rather than fees. The exchange argument below justifies making that choice greedily.

Sort projects by required capital. Maintain a max-heap of profits for all projects you can currently afford. Each step, pick the most profitable available project.

Invariant: the heap contains profits of all projects with capital <= current w not yet taken.

Algorithm (step-by-step)

1. Pair projects and sort by capital ascending.
2. For up to k rounds:
   • Push all projects with capital <= w into a max-heap.
   • If the heap is empty or its maximum available profit is nonpositive, break. Choosing fewer than k projects is allowed, and a nonpositive profit cannot improve capital or unlock a higher requirement.
   • Pop max profit and add to w.
3. Return w.

Correctness sketch

Before each selection, the heap contains all unchosen projects whose capital requirement is at most current capital. Selecting the largest positive profit maximizes capital after that round. Exchange it with the first choice of an optimal sequence: the replacement is affordable now and leaves at least as much capital, so it cannot make later affordable projects unavailable; if it appeared later, move the displaced project or omit a redundant choice under the at-most-k limit. Repeating this exchange proves greedy optimality. Because selected profits are positive, capital never decreases and the sorted eligibility pointer advances only forward. If no positive affordable profit remains, stopping is optimal: zero changes nothing and negative profit cannot unlock a higher requirement.

Trace (hand walkthrough)

Example input:
k = 2, w = 0
profits = [1,2,3]
capital = [0,1,1]
Output: 4

Walk:
- w=0: feasible profits [1] -> pick 1 -> w=1
- w=1: feasible profits [2,3] -> pick 3 -> w=4
- k=2 done -> 4

Pitfalls to avoid

• Failing to push all projects feasible at the current capital each step.
• Using a min-heap for profits (you need the max).

Debugging lens

Do not subtract required capital; it is an eligibility threshold, not a cost consumed by the model. Stop when the best available profit is nonpositive. Verify equal-length profit/capital arrays and representable accumulated capital.

Complexity

• Time: O(n log n + k log n).
• Extra space: O(n).

Implementation notes (Go)

• Sort projects by capital and push feasible profits into a max-heap.
• Each round, take the highest profit project available.

Contract precision

Capital requirements are thresholds; completing a project adds its profit without subtracting its requirement. Each project is chosen at most once. Declining nonpositive projects respects the at-most-k contract; chosen profits only increase capital, so the maximum-final-capital guarantee bounds intermediate values too.

Reconstruction checkpoint

With w=0, k=2, requirements [0,1,1], and profits [1,2,3], what is selected? Should a negative-profit affordable project ever be required?

Return to Heap / Priority Queue · Module quiz