Maximize Capital

A busy investor with an initial capital, c, needs an automated investment program. They can select k distinct projects from a list of n projects with corresponding capitals requirements and expected profits. For a given project i, its capital requirement is capitals[i], and the profit it yields is profits[i].

Statement

A busy investor with an initial capital, c, needs an automated investment program. They can select k distinct projects from a list of n projects with corresponding capitals requirements and expected profits. For a given project i, its capital requirement is capitals[i], and the profit it yields is profits[i].

The goal is to maximize their cumulative capital by selecting a maximum of k distinct projects to invest in, subject to the constraint that the investor's current capital must be greater than or equal to the capital requirement of all selected projects.

When a selected project from the identified ones is finished, the pure profit from the project, along with the starting capital of that project, is returned to the investor. This amount will be added to the total capital held by the investor. Now, the investor can invest in more projects with the new total capital. It is important to note that each project can only be invested in once.

As a basic risk-mitigation measure, the investor wants to limit the number of projects they invest in. For example, if k is 2, the program should identify the two projects that maximize the investor's profits while ensuring that the investor's capital is sufficient to invest in the projects.

Overall, the program should help the investor make informed investment decisions by picking a list of a maximum of k distinct projects to maximize the final profit while mitigating risk.

Constraints

• 1 ≤ k ≤ 10³
• 0 ≤ c ≤ 10⁹
• 1 ≤ n ≤ 10³
• k ≤ n
• n == profits.length
• n == capitals.length
• 0 ≤ profits[i] ≤ 10⁴
• 0 ≤ capitals[i] ≤ 10⁹

Examples

Example 1

Input: k = 2, c = 0 profits = [1, 2, 3] capitals = [0, 1, 1]

Explanation:

• With c = 0, only the project with capitals[0] = 0 is affordable, yielding a profit of 1. New capital = 0 + 1 = 1.
• With c = 1, projects at index 1 (capitals = 1, profit = 2) and index 2 (capitals = 1, profit = 3) are both affordable. Since only 1 more project can be picked (k = 2 total), pick the one with the higher profit: index 2, profit 3. New capital = 1 + 3 = 4.

Output: 4

Example 2

Input: k = 3, c = 0 profits = [1, 2, 3] capitals = [0, 1, 2]

Explanation:

• Start with c = 0: only project 0 is affordable (profit = 1). Capital becomes 1.
• Now c = 1: project 1 is affordable (profit = 2). Capital becomes 3.
• Now c = 3: project 2 is affordable (profit = 3). Capital becomes 6.
• All k = 3 projects have been used.

Output: 6

Maximum Capital

Solution

The steps to solve this problem:

• First, we build a min heap using all the project capitals (the money needed to start each project).
• We also create an empty max heap to store profits.
• We can only do k transactions (projects), so we run a loop k times.
• Inside this loop, we run another loop:
  • We check if the smallest capital in the min heap is less than or equal to our current capital.
  • If yes, we remove that project from the min heap and push its profit into the max heap.
  • We keep doing this until we find a project we cannot afford, or the min heap becomes empty.
• Once this inner loop stops, it means our current capital is not enough for any more projects in the min heap.
• Now, we take the largest profit from the max heap and add it to our current capital.
• If the max heap is empty at this point, we stop early. There are no more profitable projects to pick.
• After the loop finishes, we return the final current capital.

Code

function maximumCapital(c, k, capitals, profits) {
  let currentCapital = c;
  let capitalsMinHeap = new MinHeap();
  let profitsMaxHeap = new MaxHeap();

  for (var x = 0; x < capitals.length; x++) {
    capitalsMinHeap.push([capitals[x], x]);
  }

  for (var counter = 0; counter < k; counter++) {
    while (
      capitalsMinHeap.size() > 0 &&
      capitalsMinHeap.peek()[0] <= currentCapital
    ) {
      let element = capitalsMinHeap.pop();
      c = element[0];
      let i = element[1];
      profitsMaxHeap.push([profits[i]]);
    }

    if (profitsMaxHeap.size() == 0) {
      break;
    }

    let element = profitsMaxHeap.pop();
    let j = element[0];
    currentCapital = currentCapital + j;
  }

  return currentCapital;
}