502. IPO
leetcode hard
Task
Предположим, что 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# solution
matched/originalpublic 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++ solution
auto-draft, review before submit#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 solution
matched/originalclass 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 solution
matched/originalclass 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 solution
matched/originalimport 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 solution
matched/originalfunc 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
}Explanation
Algorithm
Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.
Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.
Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.
😎