90th Percentile, Sorted Stack + MaxHeap, 9 Lines, Clean Python Solution [Explanation] [Greedy]

  • 0
            import heapq
            jobs = sorted(zip(Capital, Profits), reverse = True)
            available = []
            for i in range(k):
                while jobs and jobs[-1][0] <= W:
                    heapq.heappush(available, (-jobs.pop()[1],))
                if available:
                    W -= heapq.heappop(available)[0]
            return W

    Basic idea: Find and do the most profitable job available K times.

    First, Capital and Profit are zipped into tuples, then sorted in ascending order to create a stack where the top elements require less capital.

    Then, available jobs are popped off the stack, its profit pushed onto a maxheap with most profitable jobs on top.

    Finally, the most profitable job available gets popped and current capital gets updated.

    This process is done K times.

    Since Python does not explicitly support maxheaps, the profits are negated and pushed onto a minheap/priority queue. Encapsulating each profit into a tuple yields a speed boost over naked Integers.

Log in to reply

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