Given capital[] and profits[] for n projects, and starting capital w with k projects to pick, maximize capital by doing at most k projects (each can only be done once). Each project requires capital[i] to start and yields profit[i].
Input: k=2, w=0, profits=[1,2,3], capital=[0,1,1] → Output: 4Input: k=3, w=0, profits=[1,2,3], capital=[0,1,2] → Output: 6
Sort projects by capital. Use a max-heap of profits for affordable projects. Greedily pick the most profitable affordable project.
- Sort projects by capital requirement.
- While k > 0: push all projects with capital <= w into max-heap.
- If heap empty: cannot proceed.
- Else: pop max profit, add to w, k--.
import java.util.*;
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
int[][] projects = new int[n][2];
for (int i = 0; i < n; i++) projects[i] = new int[]{capital[i], profits[i]};
Arrays.sort(projects, (a,b) -> a[0] - b[0]);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
int i = 0;
for (int j = 0; j < k; j++) {
while (i < n && projects[i][0] <= w) maxHeap.offer(projects[i++][1]);
if (maxHeap.isEmpty()) break;
w += maxHeap.poll();
}
return w;
}
}
- Time Complexity: O(N log N + k log N)
- Space Complexity: O(N)