Solution: IPO

Let's solve the IPO problem using the Heaps pattern.

Statement

An investor is looking to maximize their capital by undertaking a set of profitable projects. Due to limited time and resources, they can complete at most k distinct projects.

There are nn available projects. Each project i has:

  • A profit of profits[i] earned upon completion.

  • A minimum capital requirement of capital[i] needed to start the project.

The investor starts with an initial capital of c. After completing a project, its profit is immediately added to the investor's current capital.

The goal is to choose up to k different projects in a way that maximizes the investor’s final capital. Return the maximum capital achievable after completing these projects.

It is guaranteed that the answer fits within a 32-bit signed integer.

Constraints:

  • 1≤1 \leq k ≤103\leq 10^3

  • 0≤0 \leq c ≤\leq 10910^9

  • n==n== profits.length

  • n==n== capitals.length

  • 1≤n ...