O(max(NK, NlogN)) algorithm, not using heap, just barely pass the OJ...


  • 1
    Z
    class Solution(object):
        def findMaximizedCapital(self, k, W, Profits, Capital):
            pc = zip(Profits, Capital)
            pc.sort(key=lambda (x, y): (-x, y))
            max_needed_capital = 0
            idx = 0
            for _ in range(k):
                for i in xrange(idx, len(pc)):
                    p, c = pc[i]
                    if c is None:
                        continue
                    max_needed_capital = max(max_needed_capital, c)
                    idx += 1
                    if max_needed_capital > W:
                        idx = 0
                    if c <= W:
                        W += p
                        pc[i] = (0, None)
                        break
                else:
                    return W
            return W
    

Log in to reply
 

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