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.

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

Core idea (near-solution)

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 heap is empty, break.
   • Pop max profit and add to w.
3. Return w.

Correctness sketch

• Invariant: the heap contains profits of all projects with capital <= current w not yet taken.
• The heap always maintains its ordering invariant.
• Pushing and popping preserves the set of best candidates so far.
• The final heap contents/top yields the correct answer.

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).

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.