PROBLEM DESCRIPTION
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. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects. You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it. Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital. Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
SOLUTION
The following solution uses two priority queues: a min heap (pqCost) to keep track of projects with the lowest capital requirements and a max heap (pqProfit) to prioritize projects with the highest profits. The code iteratively selects projects based on available capital. It checks if a project with the lowest capital requirement can be chosen and, if so, adds its profit to the max heap. It continues this process until you’ve chosen ‘k’ projects or there are no more projects with suitable capital requirements. By selecting projects with the highest profit among those with enough capital, it maximizes the final capital while considering both profit and capital constraints.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
//min heap using [capitalNeeded, indexOfTask]
//we will use this to get the tasks which have the least capital requirement
PriorityQueue<int[]> pqCost = new PriorityQueue<>( (a,b) -> a[0] - b[0] );
//add all [capital, index] pairs to the min heap
for(int i=0; i<n; i++){
pqCost.add(new int[]{capital[i], i});
}
//max heap to select the task which gives the max profit among all tasks which are currently possible
PriorityQueue<Integer> pqProfit = new PriorityQueue<>(Collections.reverseOrder());
//while we can choose more tasks
while(k>0){
//all the tasks would be present in min heap initially
//while it is not empty, let's check if the next task which the minimum capital requirement can be chosen
//if yes, then add the profit we obtain to the max heap
//keep doing this for all possible tasks
while(!pqCost.isEmpty() && pqCost.peek()[0] <= w){
int[] current = pqCost.poll();
int idx = current[1];
pqProfit.add(profits[idx]);
}
//it's possible that we don't have enough capital to choose any task in which case max heap will be empty
//we can break in that case otherwise we will go into an infinite loop
if(pqProfit.isEmpty())
break;
//otherwise do the next task possible with max profit and add to our current capital
//IMPORTANT: we will not use a while loop here because after choosing the first task itself, it's possible that we can choose other task with the current updated capital which can potentially give us more profit.
//so just add profit from the next possible task and re-update the min heap to see if we can add more tasks
else{
w += pqProfit.poll();
k--;
}
}
return w;
}
}