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
|
// 502. IPO
#include "leetcode.h"
/*
* suppose leetcode will start its ipo soon. in order to sell a good price of
* its shares to venture capital, leetcode woule 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. maximise capital
* after finishing at most 'k' distinct projects. given 'n' projects where the
* i'th project has a pure profit 'profits[i]' and min capital of 'capital[i]'
* is needed to start it.
*/
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int> &profits,
vector<int> &capital) {
priority_queue<int> pq;
int x = 0;
vector<pair<int, int>> vp;
for (int i = 0; i < profits.size(); i++)
vp.push_back({capital[i], profits[i]});
sort(vp.begin(), vp.end());
while (x < vp.size() && k) {
if (w >= vp[x].first) {
pq.push(vp[x].second);
x++;
} else {
if (pq.empty())
return w;
else {
w += pq.top();
pq.pop();
k--;
}
}
}
while (k-- && !pq.empty()) {
w += pq.top();
pq.pop();
}
return w;
}
};
int main() {
Solution obj;
vector<int> profits = {1, 2, 3};
vector<int> c1 = {0, 1, 1}, c2 = {0, 1, 2};
cout << obj.findMaximizedCapital(2, 0, profits, c1) << endl; // expect: 4
cout << obj.findMaximizedCapital(3, 0, profits, c2) << endl; // expect: 6
}
|