From bfa816e4d0bcdb3996fb4d0de074dbf71155373d Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Sat, 15 Jun 2024 12:01:21 -0600 Subject: ipo & initial gitignore --- .gitignore | 1 + a.out | Bin 15648 -> 0 bytes ipo.c | 4 +--- ipo.py | 42 ++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 44 insertions(+), 3 deletions(-) create mode 100644 .gitignore delete mode 100755 a.out create mode 100644 ipo.py 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 Binary files a/a.out and /dev/null 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 -#include -#include +#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])) -- cgit v1.2.3