Best Sequence of Capital-Limited Projects
Problem
You start with capital w and may invest in up to k projects. Project i requires capital cap[i] and yields net profit profit[i]. Pick at most k projects (one round at a time) to maximize the final capital.
Input
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]Output
4Two 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.
import heapq
def find_max_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;
}