We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delivering Boxes from Storage to Ports

Number: 1789

Difficulty: Hard

Paid? No

Companies: Nutanix

Problem Description

Given a list of boxes where each box is described by its destination port and weight, you must deliver them in order using a single ship that cannot exceed limits on the maximum number of boxes and total weight per trip. For each batch of boxes loaded (while maintaining the given order), the ship makes trips to deliver the boxes sequentially (possibly without a trip if consecutive boxes share the same port) and finally returns to storage. The goal is to determine the minimum number of trips required to deliver all boxes.

Key Insights

  • The boxes must be delivered in the order they appear, so the decision to load a certain number of boxes for each trip is crucial.
  • There are two primary constraints within each trip: the number of boxes (maxBoxes) and their total weight (maxWeight).
  • The cost (number of trips) for delivering a selected batch depends on the number of port changes within that batch; every time the destination port changes (except when consecutive boxes have the same destination), an additional trip is incurred.
  • A dynamic programming approach is well suited here since the subproblem of delivering the first i boxes can be used to build an answer for i+1 boxes.
  • Sliding window techniques can be used to determine the maximum segment of boxes that satisfy the weight and count constraints.
  • Using a monotonic queue or deque can help optimize the transitions between DP states, reducing the computational overhead of checking all possible splits.

Space and Time Complexity

Time Complexity: O(n), since we process each box once while maintaining a sliding window and a deque for DP state transitions. Space Complexity: O(n) for storing the DP array and additional data structures (like the deque).

Solution

We use dynamic programming (DP) where dp[i] represents the minimum trips required to deliver the first i boxes. For each box i, we try to determine the largest valid group (or window) ending at i that satisfies the constraints of maxBoxes and maxWeight. For each valid group from j to i, we account for:

  • The cost to deliver boxes from j to i, which is equal to the number of distinct port trips based on adjacent port changes (plus one extra trip for returning to storage).
  • The optimal previous state dp[j] that gives the minimum total trips up to that point. Thus, the recurrence becomes: dp[i + 1] = min(dp[j] + delivery_cost(j+1, i) + 1) where the +1 accounts for the return trip to storage after finishing this segment. To efficiently determine the minimal dp[j] for valid j’s, we use a deque (monotonic queue) to maintain candidates in order such that we can update the DP in O(1) average time per box. Key details/tricks:
  • Maintain running totals of weight and a count of port changes as the window extends.
  • When the addition of a new box violates the constraints, shrink the window by moving the left pointer.
  • Update the monotonic queue to ensure that only promising DP states (which yield a lower overall cost) are considered. This approach ensures that we cover the delivery cost efficiently and adhere to the box ordering as well as the capacity limits.

Code Solutions

# Python solution

class Solution:
    def boxDelivering(self, boxes, portsCount, maxBoxes, maxWeight):
        n = len(boxes)
        # dp[i] will be the minimum trips required for boxes[0:i]
        dp = [0] * (n + 1)
        # cnt[i] stores the incremental cost (i.e., extra trips between different ports) 
        diff = [0] * (n + 1)  
        for i in range(1, n):
            # if current box has a different port than the previous one, add a trip cost.
            diff[i] = diff[i - 1] + (1 if boxes[i][0] != boxes[i - 1][0] else 0)
        
        # Use two pointers to maintain a valid window (j -> i) meeting maxBoxes and maxWeight constraints.
        j = 0
        totalWeight = 0
        from collections import deque
        # The deque will store indices j as candidates for transition (monotonic increasing in dp[j]-diff[j])
        monoQueue = deque()
        dp[0] = 0
        monoQueue.append(0)
        
        for i in range(n):
            totalWeight += boxes[i][1]
            # Ensure window [j, i] respects constraints: number of boxes and total weight.
            while (i - j + 1 > maxBoxes) or (totalWeight > maxWeight):
                totalWeight -= boxes[j][1]
                # If the candidate j is at the head of the deque, remove it.
                if monoQueue and monoQueue[0] == j:
                    monoQueue.popleft()
                j += 1
            
            # Compute dp[i+1] from best candidate in the current window.
            # dp[i+1] = dp[j] + extra cost (diff[i] - diff[j]) + 2 (1 for delivery trips, 1 for return)
            # But here we postpone the return trip addition until the end.
            dp[i + 1] = monoQueue and (dp[monoQueue[0]] - diff[monoQueue[0]] + diff[i] + 2) or float('inf')
            
            # If next box exists and has same port as current, we might subtract one extra trip.
            # This is because if boxes[i+1] has same destination as boxes[i], we can deliver in one go.
            if i + 1 < n and boxes[i][0] == boxes[i + 1][0]:
                dp[i + 1] -= 1
            
            # Maintain the monotonic queue: remove indices from the back that are not better than current state.
            while monoQueue and (dp[monoQueue[-1]] - diff[monoQueue[-1]]) >= (dp[i + 1] - diff[i + 1]):
                monoQueue.pop()
            monoQueue.append(i + 1)
        
        return dp[n]

# Example usage:
# sol = Solution()
# print(sol.boxDelivering([[1,1],[2,1],[1,1]], 2, 3, 3))
← Back to All Questions