IPO Maximize Capital

Select projects to maximize final capital with limited initial funds.

greedy heap sorting capital

You are given an initial capital `w` and a list of `n` projects. Each project `i` has a capital requirement `capital[i]` (the minimum capital needed to start it) and a pure profit `profits[i]` (added to your capital upon completion). You may select **at most `k`** projects, and you can only start a project if your current capital is at least its capital requirement. You may complete projects in any order, and each project can be taken at most once.

Implement the function:
```python
def find_maximized_capital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
```

Return the maximum possible capital after completing **at most `k`** projects. It is guaranteed that the total capital will fit in a 32-bit signed integer.

**Note:** You are not required to take exactly `k` projects; if no more projects can be started, you stop.

Constraints

<= k <= 10^5
<= w <= 10^9
<= n <= 10^5
<= profits[i] <= 10^4
<= capital[i] <= 10^9
It is guaranteed that the final capital fits in a 32-bit signed integer.

Your solution should run in O(n log n) time or better.

Example

>>> find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1])
4
>>> find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2])
6
>>> find_maximized_capital(1, 2, [3, 4], [5, 1])
6

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think greedily: at each step, choose the most profitable project you can afford.

Sort projects by capital requirement. Use a max-heap to store profits of affordable projects.

The heap should always contain all projects whose capital requirement is <= current capital.

If the heap is empty, break early—no more projects can be started.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.