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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delivering Boxes from Storage to Ports

Difficulty: Hard

Problem Description

You have the task of delivering some boxes from storage to their ports using only one ship. However, this ship has a limit on the number of boxes and the total weight that it can carry. You are given an array boxes, where boxes[i] = [ports​i​, weight​i​], and three integers portsCount, maxBoxes, and maxWeight. The boxes need to be delivered in the order they are given. Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.

Key Insights

  • The boxes must be delivered in the order they are given.
  • The ship can only carry a limited number of boxes and a limited total weight.
  • Each delivery trip to a port counts as one trip, and returning to storage counts as another trip.
  • We can optimize the number of trips by carefully selecting how many boxes to take based on the constraints.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of boxes. We process each box at most twice (once when loading and once when delivering). Space Complexity: O(1) - we only use a few variables for tracking counts and weights, not dependent on input size.

Solution

To solve the problem, we will use a greedy algorithm. We will iterate through the boxes while maintaining a count of the current weight and the number of boxes being loaded. When we reach the limit for either the maximum number of boxes or the maximum weight, we will deliver the boxes to their respective ports. For each delivery, we will track the number of trips taken, which includes both going to the port and returning to storage. We will continue this process until all boxes are delivered.

Code Solutions

def boxDelivering(boxes, portsCount, maxBoxes, maxWeight):
    trips = 0
    currentWeight = 0
    currentBoxes = 0
    lastPort = None
    
    for i in range(len(boxes)):
        port, weight = boxes[i]

        if currentBoxes < maxBoxes and currentWeight + weight <= maxWeight:
            # Load the box
            currentWeight += weight
            currentBoxes += 1
        else:
            # Make trips for current loaded boxes
            trips += 1  # Trip to deliver current batch
            if lastPort is not None and lastPort != port:
                trips += 1  # Return trip to storage
            # Reset for new load
            currentWeight = weight
            currentBoxes = 1
        
        lastPort = port

    # Deliver remaining boxes
    trips += 1  # Final trip to deliver last batch
    if lastPort is not None:
        trips += 1  # Return trip to storage if needed

    return trips
← Back to All Questions