hard

IPO

Pick projects to maximize capital using a two-heap greedy strategy under a budget.

1. Define the problem

IPO

You have w initial capital and can complete at most k distinct projects before your IPO. Each project i has a required capitali and yields profiti once finished. You may only start a project if your current capital is at least its required capital . Return the maximized final capital after choosing at most k projects. Sort projects by required capital, then greedily use a max-heap of profits over every project currently affordable — always taking the most profitable one available.

Constraints

  • 1 ≤ k ≤ 105
  • 0 ≤ w ≤ 109
  • n == profits.length == capitals.length
  • 1 ≤ n ≤ 105
  • 0 ≤ profitsi ≤ 104
  • 0 ≤ capitalsi ≤ 109

Example

Inputk = 2, w = 0, profits = [1, 2, 3], capitals = [0, 1, 1]
Output4

Explanation With capital 0, only the project needing 0 capital is affordable — take it (profit 1), capital becomes 1. Now both remaining projects are affordable — take the one with profit 3, capital becomes 4.

2. Know the words first

In plain terms

Greedy by profit, unlocked by capital
At each of the k rounds, every project whose capital requirement is already met becomes available. Taking the highest-profit one available is always at least as good as taking any other, since capital only grows.
3. Visualize the solution

Unlock projects by capital, always take the biggest profit available

Unlock projects by capital, always take the biggest profit available
Statussorted by capital

Projects sorted by required capital: (0, profit 1), (1, profit 2), (1, profit 3). The profit heap is still empty.

What happens in this step

sort by capital: [cap 0, profit 1], [cap 1, profit 2], [cap 1, profit 3]

Capital 0 unlocks the first project immediately; capital 1 unlocks the next two (tie broken by original order). Nothing has been pushed into the profit heap yet, so all three slots of the row below are empty.
Step 1 of 4

Steps to visualize

  1. Sort every project by the capital it requires, ascending.
  2. The row is the profit heap: three slots, one per project. A slot marked — is empty.
  3. For each of the k rounds, push every project now affordable (capital requirement met) into a max-heap of profits.
  4. Pop the most profitable available project and add its profit to your capital.
  5. Stop early if no project is affordable.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Unlock projects by capital, always take the biggest profit available
Statussorted by capital

Projects sorted by required capital: (0, profit 1), (1, profit 2), (1, profit 3). The profit heap is still empty.

What happens in this step

sort by capital: [cap 0, profit 1], [cap 1, profit 2], [cap 1, profit 3]

Capital 0 unlocks the first project immediately; capital 1 unlocks the next two (tie broken by original order). Nothing has been pushed into the profit heap yet, so all three slots of the row below are empty.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findMaximizedCapital(k, w, profits, capitals) {
  const n = profits.length;
  const projects = [];
  for (let i = 0; i < n; i++) projects.push([capitals[i], profits[i]]);
  projects.sort((a, b) => a[0] - b[0]);

  const heap = []; // max-heap of profits

  function push(val) {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent] < heap[i]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDown() {
    let i = 0;
    const size = heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left] > heap[largest]) largest = left;
      if (right < size && heap[right] > heap[largest]) largest = right;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  }

  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDown();
    }
    return top;
  }

  let capital = w;
  let index = 0;

  for (let round = 0; round < k; round++) {
    while (index < n && projects[index][0] <= capital) {
      push(projects[index][1]);
      index++;
    }
    if (heap.length === 0) break;
    capital += pop();
  }

  return capital;
}
Time
O(n log n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
k = 2, w = 0, profits = [1, 2, 3], capitals = [0, 1, 1]4example from the docstring
k = 1, w = 5, profits = [2, 5, 8], capitals = [0, 1, 5]13starting capital immediately unlocks the most profitable project
k = 0, w = 10, profits = [1], capitals = [0]10no projects can be completed, capital is unchanged
k = 3, w = 0, profits = [5], capitals = [1]0no project is ever affordable, loop exits early
k = 3, w = 0, profits = [1, 2, 3, 5], capitals = [0, 0, 0, 0]10every project is affordable from the start, always take the biggest profit
k = 5, w = 0, profits = [1, 2], capitals = [0, 0]3k is larger than the number of projects, stops once all are used

Keep reading