# LeetCode 502: IPO

## Problem Restatement

We are given `n` projects.

Each project has:

| Array | Meaning |
|---|---|
| `profits[i]` | The pure profit gained after finishing project `i` |
| `capital[i]` | The minimum capital needed to start project `i` |

We start with capital `w`.

We can finish at most `k` distinct projects.

After finishing a project, its profit is added to our capital.

We need to return the maximum final capital possible after choosing at most `k` projects.

The problem asks us to maximize total capital after doing up to `k` projects, where each project requires some starting capital and gives profit after completion. The final answer fits in a 32-bit signed integer.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `k`, `w`, `profits`, `capital` |
| Output | Maximum final capital |
| Rule | A project can be chosen at most once |
| Limit | Choose at most `k` projects |

Function shape:

```python
class Solution:
    def findMaximizedCapital(
        self,
        k: int,
        w: int,
        profits: List[int],
        capital: List[int],
    ) -> int:
        ...
```

## Examples

Example 1:

```python
k = 3
w = 0
profits = [1, 2, 3]
capital = [0, 1, 1]
```

At the start, we have capital `0`.

Only projects with required capital `<= 0` are available.

So we can choose project `0`:

```text
capital = 0 + 1 = 1
```

Now projects with required capital `1` are available.

We should choose the most profitable available project, profit `3`:

```text
capital = 1 + 3 = 4
```

Then choose profit `2`:

```text
capital = 4 + 2 = 6
```

The answer is:

```python
6
```

Example 2:

```python
k = 1
w = 2
profits = [1, 2, 3]
capital = [1, 1, 2]
```

All projects are affordable because their required capital is at most `2`.

We can choose only one project.

So we choose the project with profit `3`.

The answer is:

```python
5
```

## First Thought: Try All Project Orders

A direct approach is to try every possible sequence of projects.

At each step, choose one affordable unused project.

Then update capital and continue.

This explores many possible project orders.

For `n` projects and up to `k` choices, this can become very large.

Even when `k` is small, the branching factor can be high.

## Problem With Brute Force

The brute force method wastes time comparing many sequences that do not need to be compared.

At any point, if several projects are affordable, choosing the one with the highest profit is always best.

A higher profit immediately increases capital more.

More capital can only make more projects affordable, never fewer.

So we do not need to explore all affordable choices.

We should greedily choose the best profit among currently affordable projects.

## Key Insight

The problem has two requirements:

1. We need to know which projects are affordable with current capital.
2. Among affordable projects, we need to choose the largest profit.

Use two structures:

| Structure | Purpose |
|---|---|
| Sorted projects by required capital | Lets us discover newly affordable projects |
| Max heap of profits | Lets us choose the best available project |

Python has a min heap, so we store negative profits to simulate a max heap.

## Algorithm

Create project pairs:

```python
projects = sorted(zip(capital, profits))
```

Each pair is:

```text
(required_capital, profit)
```

Use an index `i` to scan projects sorted by required capital.

Use a heap `available` to store profits of projects we can currently afford.

For each of up to `k` rounds:

1. Move every project with `required_capital <= w` into the heap.
2. If the heap is empty, no project can be started, so stop.
3. Pop the largest profit from the heap.
4. Add that profit to `w`.

After the loop, return `w`.

## Correctness

At every step, the algorithm adds all projects whose required capital is at most the current capital `w` into the heap.

Therefore, the heap contains exactly the projects that are currently affordable and have not already been chosen.

The algorithm then chooses the affordable project with the largest profit.

This greedy choice is safe because choosing a larger profit gives capital at least as large as choosing any other affordable project. Since project availability depends only on current capital, having more capital cannot remove future options.

So after each chosen project, the greedy algorithm has capital at least as large as any alternative strategy that chose the same number of projects.

By repeating this argument for up to `k` projects, the algorithm produces the maximum possible final capital.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n + k log n)` | Sorting costs `O(n log n)`, heap operations cost up to `O(k log n)` plus pushes |
| Space | `O(n)` | The sorted project list and heap can store up to `n` projects |

Since each project is pushed into the heap at most once and popped at most once, this is often written as:

```text
O(n log n + k log n)
```

or simply:

```text
O((n + k) log n)
```

## Implementation

```python
from typing import List
import heapq

class Solution:
    def findMaximizedCapital(
        self,
        k: int,
        w: int,
        profits: List[int],
        capital: List[int],
    ) -> int:
        projects = sorted(zip(capital, profits))
        available = []

        i = 0
        n = len(projects)

        for _ in range(k):
            while i < n and projects[i][0] <= w:
                required_capital, profit = projects[i]
                heapq.heappush(available, -profit)
                i += 1

            if not available:
                break

            w += -heapq.heappop(available)

        return w
```

## Code Explanation

We combine the two arrays into project pairs:

```python
projects = sorted(zip(capital, profits))
```

Sorting by capital lets us move affordable projects into the heap in one pass.

The heap stores profits of projects that are currently available:

```python
available = []
```

Python’s `heapq` is a min heap.

To get max heap behavior, we push negative profits:

```python
heapq.heappush(available, -profit)
```

The pointer `i` tracks the next project not yet considered:

```python
i = 0
```

For each project selection round:

```python
for _ in range(k):
```

we move all newly affordable projects into the heap:

```python
while i < n and projects[i][0] <= w:
```

If no project is available, we cannot continue:

```python
if not available:
    break
```

Otherwise, choose the largest available profit:

```python
w += -heapq.heappop(available)
```

The negative sign converts it back to a positive profit.

Finally, return the final capital:

```python
return w
```

## Testing

```python
def test_find_maximized_capital():
    s = Solution()

    assert s.findMaximizedCapital(
        2,
        0,
        [1, 2, 3],
        [0, 1, 1],
    ) == 4

    assert s.findMaximizedCapital(
        3,
        0,
        [1, 2, 3],
        [0, 1, 1],
    ) == 6

    assert s.findMaximizedCapital(
        1,
        2,
        [1, 2, 3],
        [1, 1, 2],
    ) == 5

    assert s.findMaximizedCapital(
        3,
        0,
        [1, 2, 3],
        [1, 1, 2],
    ) == 0

    assert s.findMaximizedCapital(
        4,
        2,
        [2, 3, 1, 5, 3],
        [4, 4, 2, 3, 3],
    ) == 14

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `k = 2`, starts from `0` | Checks partial selection |
| `k = 3`, starts from `0` | Checks repeated unlocking of projects |
| Already enough capital | Chooses highest profit immediately |
| No affordable project | Returns initial capital |
| Larger mixed case | Checks heap ordering and capital unlocking |