502. IPO
Предположим, что 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.
C# решение
сопоставлено/оригиналpublic class Solution {
public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {
var projects = new List<(int capital, int profit)>();
for (int i = 0; i < profits.Length; i++) {
projects.Add((capital[i], profits[i]));
}
projects.Sort((a, b) => a.capital.CompareTo(b.capital));
var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
int ptr = 0;
for (int i = 0; i < k; i++) {
while (ptr < projects.Count && projects[ptr].capital <= w) {
maxHeap.Enqueue(projects[ptr].profit, projects[ptr].profit);
ptr++;
}
if (maxHeap.Count == 0) break;
w += maxHeap.Dequeue();
}
return w;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int FindMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
var projects = new List<(int capital, int profit)>();
for (int i = 0; i < profits.size(); i++) {
projects.push_back((capital[i], profits[i]));
}
projects.Sort((a, b) => a.capital.CompareTo(b.capital));
var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
int ptr = 0;
for (int i = 0; i < k; i++) {
while (ptr < projects.size() && projects[ptr].capital <= w) {
maxHeap.Enqueue(projects[ptr].profit, projects[ptr].profit);
ptr++;
}
if (maxHeap.size() == 0) break;
w += maxHeap.Dequeue();
}
return w;
}
}Java решение
сопоставлено/оригиналclass Solution {
class Project implements Comparable<Project> {
int capital, profit;
public Project(int capital, int profit) {
this.capital = capital;
this.profit = profit;
}
public int compareTo(Project project) {
return capital - project.capital;
}
}
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
Project[] projects = new Project[n];
for (int i = 0; i < n; i++) {
projects[i] = new Project(capital[i], profits[i]);
}
Arrays.sort(projects);
PriorityQueue<Integer> q = new PriorityQueue<Integer>(n, Collections.reverseOrder());
int ptr = 0;
for (int i = 0; i < k; i++) {
while (ptr < n && projects[ptr].capital <= w) {
q.add(projects[ptr++].profit);
}
if (q.isEmpty()) {
break;
}
w += q.poll();
}
return w;
}
}JavaScript решение
сопоставлено/оригиналclass MaxHeap {
constructor(compare) {
this.heap = [];
this.compare = compare;
}
insert(value) {
this.heap.push(value);
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(this.heap[index], this.heap[parentIndex]) <= 0) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extract() {
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
let index = 0;
const length = this.heap.length;
while (true) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let largest = index;
if (left < length && this.compare(this.heap[left], this.heap[largest]) > 0) largest = left;
if (right < length && this.compare(this.heap[right], this.heap[largest]) > 0) largest = right;
if (largest === index) break;
[this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
index = largest;
}
}
return max;
}
get size() {
return this.heap.length;
}
}
const findMaximizedCapital = (k, w, profits, capital) => {
const projects = capital.map((cap, i) => [cap, profits[i]]).sort((a, b) => a[0] - b[0]);
const maxHeap = new MaxHeap((a, b) => b - a);
let ptr = 0;
for (let i = 0; i < k; i++) {
while (ptr < projects.length && projects[ptr][0] <= w) {
maxHeap.insert(projects[ptr][1]);
ptr++;
}
if (maxHeap.size === 0) break;
w += maxHeap.extract();
}
return w;
};Python решение
сопоставлено/оригиналimport heapq
class Solution:
def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
projects = sorted(zip(capital, profits))
max_heap = []
ptr = 0
for _ in range(k):
while ptr < len(projects) and projects[ptr][0] <= w:
heapq.heappush(max_heap, -projects[ptr][1])
ptr += 1
if not max_heap:
break
w -= heapq.heappop(max_heap)
return wGo решение
сопоставлено/оригиналfunc findMaximizedCapital(k int, w int, profits []int, capital []int) int {
projects := make([][2]int, len(profits))
for i := range profits {
projects[i] = [2]int{capital[i], profits[i]}
}
sort.Slice(projects, func(i, j int) bool {
return projects[i][0] < projects[j][0]
})
maxHeap := &MaxHeap{}
heap.Init(maxHeap)
ptr := 0
for i := 0; i < k; i++ {
for ptr < len(projects) && projects[ptr][0] <= w {
heap.Push(maxHeap, projects[ptr][1])
ptr++
}
if maxHeap.Len() == 0 {
break
}
w += heap.Pop(maxHeap).(int)
}
return w
}
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}Algorithm
Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.
Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.
Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.