aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rwxr-xr-xa.outbin15648 -> 0 bytes
-rw-r--r--ipo.c4
-rw-r--r--ipo.py42
4 files changed, 44 insertions, 3 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..cba7efc
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+a.out
diff --git a/a.out b/a.out
deleted file mode 100755
index bc26851..0000000
--- a/a.out
+++ /dev/null
Binary files differ
diff --git a/ipo.c b/ipo.c
index 5e7604b..f856d78 100644
--- a/ipo.c
+++ b/ipo.c
@@ -1,7 +1,5 @@
// 502. IPO
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* suppose leetcode will start its ipo soon. in order to sell a good price of
diff --git a/ipo.py b/ipo.py
new file mode 100644
index 0000000..0dd727f
--- /dev/null
+++ b/ipo.py
@@ -0,0 +1,42 @@
+# 502. IPO
+import heapq
+
+"""
+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(object):
+ def findMaximizedCapital(self, k, w, profits, capital):
+ """
+ :type k: int
+ :type w: int
+ :type profits: List[int]
+ :type capital: List[int]
+ :rtype: int
+ """
+ n, i = len(profits), 0
+ projects = [(capital[i], profits[i]) for i in range(n)]
+ projects.sort()
+ maximise_capital = []
+ while k > 0:
+ while i < n and projects[i][0] <= w:
+ heapq.heappush(maximise_capital, -projects[i][1])
+ i += 1
+ if not maximise_capital:
+ break
+ w -= heapq.heappop(maximise_capital)
+ k -= 1
+ return w
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findMaximizedCapital(k=2, w=0, profits=[1, 2, 3], capital=[0, 1, 1]))
+ print(obj.findMaximizedCapital(k=3, w=0, profits=[1, 2, 3], capital=[0, 1, 2]))