Сложность: hard
Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов.
Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала.
Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу.
Выберите список из не более чем k различных проектов из данных, чтобы максимально увеличить ваш конечный капитал, и верните окончательно максимизированный капитал.
Ответ гарантированно поместится в 32-битное целое число со знаком.
Пример:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
👨💻 Алгоритм:
1⃣Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.
2⃣Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.
3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.
😎 Решение:
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
vector<pair<int, int>> projects;
for (int i = 0; i < profits.size(); ++i) {
projects.emplace_back(capital[i], profits[i]);
}
sort(projects.begin(), projects.end());
priority_queue<int> maxHeap;
int ptr = 0;
for (int i = 0; i < k; ++i) {
while (ptr < projects.size() && projects[ptr].first <= w) {
maxHeap.push(projects[ptr].second);
ptr++;
}
if (maxHeap.empty()) break;
w += maxHeap.top();
maxHeap.pop();
}
return w;
}
};Ставь 👍 и забирай 📚 Базу знаний