Skip to content

Latest commit

 

History

History

502-IPO

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

IPO

Problem can be found in here!

Solution: Heap

def findMaximizedCapital(k: int, w: int, profits: List[int], capital: List[int]) -> int:
    n = len(profits)
    projects = sorted(zip(capital, profits))
    max_heap = []
    pointer = 0
    for _ in range(k):
        while pointer < n and projects[pointer][0] <= w:
            heappush(max_heap, -projects[pointer][1])
            pointer += 1
        if not max_heap:
            break

        w += -heappop(max_heap)

    return w

Time Complexity: O(nlogn), Space Complexity: O(n), where n is the length of array profits.