9 lines clean and easy to understand python single heap solution with explaination


  • 0
    Z

    The idea is very simple, first sort the projects by capital, for each "k", we load only valid projects into the max heap, the heap keeps best profit projects on the top.

    def findMaximizedCapital(k, W, Profits, Capital):
        pc = sorted(zip(Capital, Profits))
        i, heap = 0, []
        for _ in range(k):
            while i < len(pc) and pc[i][0] <= W:
                heapq.heappush(heap, -pc[i][1])
                i += 1
            if not heap: return W
            W += -heapq.heappop(heap)
        return W
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.