aboutsummaryrefslogtreecommitdiff
path: root/other/ipo.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/ipo.cpp')
-rw-r--r--other/ipo.cpp52
1 files changed, 0 insertions, 52 deletions
diff --git a/other/ipo.cpp b/other/ipo.cpp
deleted file mode 100644
index 61d5baa..0000000
--- a/other/ipo.cpp
+++ /dev/null
@@ -1,52 +0,0 @@
-// 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
-}