LC-1687 Hard LeetCode

1687. Delivering Boxes from Storage to Ports

Array Dynamic Programming Segment Tree Queue Heap (Priority Queue) Prefix Sum Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 39% Topics: Array, Dynamic Programming, Segment Tree, Queue, Heap (Priority Queue), Prefix Sum, Monotonic Queue

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Segment & Fenwick Trees 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def boxDelivering(self, boxes, portsCount, maxBoxes, maxWeight):
        """
        :type boxes: List[List[int]]
        :type portsCount: int
        :type maxBoxes: int
        :type maxWeight: int
        :rtype: int
        """
        dp = [0]*(len(boxes)+1)
        left, cost, curr = 0, 1, 0
        for right in xrange(len(boxes)):
            if right == 0 or boxes[right][0] != boxes[right-1][0]:
                cost += 1
            curr += boxes[right][1]
            while right-left+1 > maxBoxes or \
                  curr > maxWeight or \
                  (left+1 < right+1 and dp[left+1] == dp[left]):  # greedily drop box to make cost as smaller as possible
                curr -= boxes[left][1]
                if boxes[left+1][0] != boxes[left][0]:
                    cost -= 1
                left += 1
            dp[right+1] = dp[(left-1)+1] + cost
        return dp[len(boxes)]

Solution from kamyu104/LeetCode-Solutions · MIT