IPO

hard heap greedy

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO.

Inputk = 2, w = 0, profits = [1,2,3], capital = [0,1,1]

Output4

Two heaps: a min-heap of (capital, profit) for unaffordable projects, and a max-heap of profits for affordable ones. Each round, move all newly affordable projects into the max-heap and take its top.

profits

capital

import heapq

def find_maximized_capital(k, w, profits, capital):
    by_cap = sorted(zip(capital, profits))
    affordable = []  # max-heap of profits (negated)
    i = 0
    for _ in range(k):
        while i < len(by_cap) and by_cap[i][0] <= w:
            heapq.heappush(affordable, -by_cap[i][1])
            i += 1
        if not affordable: break
        w += -heapq.heappop(affordable)
    return w

// Uses a simple binary max-heap class (omitted here for brevity).
function findMaximizedCapital(k, w, profits, capital) {
  const byCap = capital.map((c, i) => [c, profits[i]]).sort((a, b) => a[0] - b[0]);
  const affordable = new MaxHeap();
  let i = 0;
  for (let r = 0; r < k; r++) {
    while (i < byCap.length && byCap[i][0] <= w) affordable.push(byCap[i++][1]);
    if (affordable.size() === 0) break;
    w += affordable.pop();
  }
  return w;
}

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> capital[a] - capital[b]);
        PriorityQueue<Integer> aff = new PriorityQueue<>((a, b) -> b - a);
        int i = 0;
        for (int r = 0; r < k; r++) {
            while (i < n && capital[idx[i]] <= w) aff.add(profits[idx[i++]]);
            if (aff.isEmpty()) break;
            w += aff.poll();
        }
        return w;
    }
}

int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    int n = profits.size();
    vector<pair<int,int>> byCap(n);
    for (int i = 0; i < n; i++) byCap[i] = {capital[i], profits[i]};
    sort(byCap.begin(), byCap.end());
    priority_queue<int> aff;
    int i = 0;
    for (int r = 0; r < k; r++) {
        while (i < n && byCap[i].first <= w) aff.push(byCap[i++].second);
        if (aff.empty()) break;
        w += aff.top(); aff.pop();
    }
    return w;
}

Explanation

We get to do at most k projects, and each finished project adds its profit to our money w. Since money only grows, the greedy move is: each round, do the single affordable project with the biggest profit.

The catch is that a project is only affordable if its required capital is at most our current w, and w changes as we earn. So we first sort the projects by their capital requirement. Then we sweep a pointer forward and unlock every project whose capital is now within reach.

Unlocked projects go into a max-heap of profits (in Python we push -profit because Python heaps are min-heaps). When it is time to pick, we pop the heap top — the largest profit we can currently afford — and add it to w.

Example: k=2, w=0, profits=[1,2,3], capital=[0,1,1]. At w=0 only the project needing capital 0 (profit 1) is affordable, so we do it and w becomes 1. Now both remaining projects (profits 2 and 3) are affordable; the heap hands us 3, so w becomes 4.

If at any round the heap is empty, no project is affordable, so we stop early. Sorting plus heap operations give an efficient solution without ever re-scanning all projects.

Time: O((n + k) log n) Space: O(n)