Problem Statement in English

You’re given n projects where the i-th project has a pure profit of profits[i] and a minimum capital of capital[i] required to start it.

Initially, you have w capital. When you finish a project, you earn the profit for that project, and your capital increases by that profit.

Approach

The intuition is this: at each step we can only choose a project that we can afford with our current capital.

Among all the projects we can afford, we should choose the one that gives us the maximum profit.

So we use two heaps:

  1. A min-heap to keep track of projects sorted by their capital requirements.
  2. A max-heap to keep track of the profits of the projects we can afford.

Everytime our capital increases, we check the min-heap for any new projects we can now afford and move them to the max-heap. Then we select the project with the maximum profit from the max-heap.

We do this for k iterations or until we can no longer afford any projects.

Solution in Python


class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        minheap = [(c, p) for c, p in zip(capital, profits)]
        maxheap = []

        heapify(minheap)

        while k:
            while minheap and minheap[0][0] <= w:
                heappush(maxheap, -heappop(minheap)[1])
            if not maxheap:
                break
            x = -heappop(maxheap)
            w += x
            k -= 1

        return w

Complexity

  • Time: $O(k \log n)$
    Since we may perform up to k iterations, and in each iteration we may need to push/pop from the heaps which takes $O(\log n)$ time.

  • Space: $O(n)$
    Since we are using two heaps to store the capital and profits.

Mistakes I Made

I did some big brain overthinking.

And we are done.