IPO
You are given a list of projects with their respective profits and capital requirements. You have a limited amount of capital and you want to invest in the projects that will give you the maximum profit. You can only invest in a project if you have enough capital. Find the maximum profit you can get.
Constraints:
- 1 <= projects.length <= 10^5
- 1 <= profits.length <= 10^5
- 1 <= capital.length <= 10^5
- 0 <= profits[i] <= 10^5
- 0 <= capital[i] <= 10^5
- 1 <= number of projects <= 10^5
Examples:
Input: [[1,2,3],[1,1,2]]
Output: 4
Explanation: The maximum profit is 4, which can be achieved by investing in the projects with profits 1 and 3.
Solutions
Greedy
The solution uses a greedy approach to find the maximum profit. It first sorts the projects based on their profits in descending order. Then it uses a priority queue to store the projects that can be invested in. The priority queue is sorted based on the profits of the projects. The solution then iterates over the projects and invests in the project with the highest profit that can be invested in. The capital is updated after each investment.
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int[][] projects = new int[profits.length][2];
for (int i = 0;
i < profits.length;
i++) {
projects[i][0] = profits[i];
projects[i][1] = capital[i];
}
Arrays.sort(projects, (a, b) -> b[0] - a[0]);
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
int index = 0;
int result = 0;
while (k > 0) {
while (index < projects.length && projects[index][1] <= w) {
queue.add(projects[index][0]);
index++;
}
if (queue.isEmpty()) {
break;
}
result += queue.poll();
k--;
w += queue.poll();
}
return result;
}Follow-up:
What if the projects have different durations and the goal is to maximize the profit within a certain time limit?
