1736. Throw garbage

LintCode 炼码

从大袋子拿起，如果拿完了还可以再拿一个，那就带上，不然就直接走。

排序了再开始拿，方便操作。

class Solution:
    """
    @param BagList: the weight of all garbage bags.
    @return: an integer represent the minimum number of times.
    """
    def Count_ThrowTimes(self, BagList):
        res = 0
        q = collections.deque(sorted(BagList))
        while q:
            bag = q.pop()
            if q and bag + q[0] <= 3.0:
                q.popleft()
            res += 1
        
        return res

想要用 heap 直接 inplace 操作的，省去sort用的O(N)空间，但不知道咋回事儿总有 test case 过不去... 代码先放着了我慢慢研究 debug.

class Solution:
    def Count_ThrowTimes(self, BagList):
        
        res = 0
        heapq.heapify(BagList)
        
        while BagList:
            bag = BagList.pop()
            if BagList and bag + BagList[0] <= 3.0:
                heapq.heappop(BagList)
            res += 1
        
        return res