1687. Delivering Boxes from Storage to Ports


Problem Description

In this problem, we are tasked with delivering a number of boxes from storage to their respective ports using a single ship. Each box has a specific port destination and a weight. We are given these details in the form of an array, boxes, where boxes[i] contains two elements: ports_i, the port where the ith box needs to be delivered to, and weight_i, the weight of the ith box.

There are three additional constraints provided:

  1. portsCount, which is the total number of different ports.
  2. maxBoxes, which is the maximum number of boxes the ship can carry during one trip.
  3. maxWeight, which is the maximum total weight of boxes the ship can carry during one trip.

The problem requires the boxes to be delivered in the exact order they are presented in the boxes array. The ship will make trips back and forth between the storage and the ports, adhering to the limits on box count and weight per trip.

The delivery process has the following steps:

  • Load the ship with boxes from the queue without exceeding the maximum allowed number of boxes and weight.
  • Deliver each box in the order they were loaded. If the ship is already at the correct port for a box, it is delivered immediately without an extra trip.
  • Return to storage to pick up more boxes.

The objective is to find the minimum number of trips that the ship must make to deliver all the boxes to their respective ports and then return to storage.

Intuition

The intuition behind solving this problem stems from the need to minimize the number of trips made by the ship. To achieve this, we must intelligently decide how many boxes to load on each trip, considering the sequential delivery requirement, weight constraints, and the possibility of delivering multiple boxes without additional trips if they are for the same or consecutive ports.

A naive approach might load the ship with the maximum number of boxes or weight allowed in every trip. However, this doesn't take into account the distribution of port destinations, which can lead to unnecessary trips. For example, loading fewer boxes might result in fewer trips if it avoids returning to a port that was visited on the previous trip.

The solution uses dynamic programming where f[i] represents the minimum number of trips to deliver the first i boxes. We iterate through the boxes and maintain a queue, q, which helps us to quickly find the optimal number of boxes to load on the ship for the next trip.

The dynamic programming approach considers:

  • The weight and box count constraints.
  • The sequence of ports to minimize trips.
  • The total number of port changes as we accumulate boxes for delivery, which impacts the trip count.

To optimize the number of trips, we leverage a sliding window technique where the queue holds indices of the boxes signifying potential starting points for a trip. When considering a new box to add to our trip, we ensure it doesn't break the maxBoxes and maxWeight limits. We update f[i] based on the number of port changes and previous trips counted in f[q[0]]. The optimization focuses on finding the least number of trips made for delivering a set of boxes by maintaining the queue in a way it always contains the best starting point for the upcoming boxes.

This approach is efficient and accounts for all given constraints, arriving at the minimum number of trips needed for delivery of all boxes.

Solution Approach

The implementation begins by preprocessing the boxes list to prepare for the dynamic programming solution. Data structures, algorithms, and patterns used are explained step-by-step below:

  1. Accumulate Weights: The accumulate function is employed to calculate running totals of the weights of the boxes, which helps in quickly checking if adding another box will exceed the maxWeight limit.

    1ws = list(accumulate((box[1] for box in boxes), initial=0))

    Here, ws[i] represents the total weight of the i boxes from the start.

  2. Calculate Port Changes: We compute the number of port changes using a list comprehension that compares the current port with the next one.

    1c = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]

    Then, the running total of port changes is accumulated in cs.

    1cs = list(accumulate(c, initial=0))

    cs[i] now indicates the total number of port changes after delivering i boxes.

  3. Dynamic Programming Array: An array f is initialized with zeros where f[i] will eventually hold the minimum number of trips needed to deliver the first i boxes.

    1f = [0] * (n + 1)
  4. Deque for Efficient Queue Management: A deque q is initialized, representing potential starting points for each batch of boxes loaded onto the ship.

    1q = deque([0])

As we iterate through boxes:

a. If the current box cannot be added without breaking the max weight or count constraints (i - q[0] > maxBoxes or ws[i] - ws[q[0]] > maxWeight), the least recent starting point is discarded from q.

b. The minimum number of trips for delivering i boxes, f[i], is then calculated by adding two trips (to and from the storage) to the difference in port changes plus the number of trips required for delivering previous batch of boxes f[q[0]].

1f[i] = cs[i - 1] + f[q[0]] - cs[q[0]] + 2

c. Before considering the next box, the implementation updates the queue by removing less efficient starting points. Essentially, we pop out any indices from the end of the queue if they don't provide a lower trip count after delivering the current set of boxes.

1while q and f[q[-1]] - cs[q[-1]] >= f[i] - cs[i]:
2    q.pop()
3q.append(i)

This ensures that q always has the best candidate for the next trip's starting point.

Finally, f[n] holds the minimum number of trips needed to deliver all n boxes. This value is what the function returns.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described in the content for better understanding:

Suppose we have the following inputs:

  • boxes = [(1, 1), (2, 2), (1, 3)] - Each tuple represents a box with its port destination and weight.
  • portsCount = 2
  • maxBoxes = 3
  • maxWeight = 3

Using the provided information, let's start following the steps of the solution:

  1. Accumulate Weights: We calculate the running total weights of the boxes to ensure we do not exceed maxWeight.

    ws = [0, 1, 3, 6]

    After adding each box, the total weights are 0 (initial), 1, 3, and 6, respectively.

  2. Calculate Port Changes: Next, we determine the number of port changes as we add boxes sequentially.

    c = [0, 1, 1] - There is no port change between the first box and itself, a change between the first and second ports, and a change back to the first port for the third box. cs = [0, 0, 1, 2]

    Now, cs tells us that the cumulative port changes after delivering each set of boxes are 0, 0, 1, and 2, respectively.

  3. Dynamic Programming Array: We initialize the array f which will store the minimum number of trips needed.

    f = [0, 0, 0, 0] - One element for each box plus the initial state.

  4. Deque for Efficient Queue Management: We initialize the queue q with the starting point.

    q = deque([0]) - Represents the starting point for loading boxes onto the ship.

As we iterate through each box using the boxes index i:

a. Check constraints: For box i = 1, there is no need to remove the starting point since the box can fit with respect to maxBoxes and maxWeight. This step would only be applied if constraints were violated.

b. Calculate minimum trips: We calculate the number of trips for delivering i = 1 box.

f[1] = cs[0] + f[q[0]] - cs[q[0]] + 2 = 0 + 0 - 0 + 2 = 2

It takes two trips to deliver the first box (one to the port and one back to storage).

c. Update the queue: For i = 1, there are no inefficient starting points in q, so we simply add the index:

q.append(1)

The queue now has q = deque([0, 1]).

Repeating the steps for i = 2 and i = 3, we find that:

  • We can't take the third box in the same trip due to maxWeight constraints, so we’ll only deliver the first two boxes in the initial trip. That will give us a total of cs[1] + f[q[0]] - cs[q[0]] + 2 = 1 + 0 - 0 + 2 = 3 trips for i = 2.
  • Then, we'll make one more trip to deliver the third box, returning to the first port.

After iterating through all boxes, we find that f[3], which is the total number of trips needed to deliver all three boxes, equals 4.

In this example, the minimum number of trips needed to deliver all the boxes to their respective ports would be 4. We made two trips for the first two boxes due to port change and weight constraints, and two additional trips to deliver the third box and return to storage.

Python Solution

1from itertools import accumulate
2from collections import deque
3from itertools import pairwise
4
5class Solution:
6    def boxDelivering(
7        self, boxes: List[List[int]], ports_count: int, max_boxes: int, max_weight: int
8    ) -> int:
9        num_boxes = len(boxes)
10      
11        # Accumulate weights of boxes for calculating the total weight in a subsequence
12        accumulated_weights = list(accumulate((box[1] for box in boxes), initial=0))
13      
14        # Count port changes by comparing consecutive boxes, 1 for a change, 0 otherwise
15        port_changes = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]
16        # Accumulate port changes to use them for calculating trips needed for subsequence of boxes
17        accumulated_changes = list(accumulate(port_changes, initial=0))
18      
19        # Array to hold the minimum number of trips needed to carry first i boxes
20        min_trips = [0] * (num_boxes + 1)
21      
22        # Deque to keep track of "candidates" for starting the subsequence
23        candidates = deque([0])
24      
25        for i in range(1, num_boxes + 1):
26            # Remove candidates that exceed max boxes or max weight constraints
27            while candidates and (i - candidates[0] > max_boxes or accumulated_weights[i] - accumulated_weights[candidates[0]] > max_weight):
28                candidates.popleft()
29          
30            # Calculate trips needed based on the best previous candidate
31            if candidates:
32                min_trips[i] = accumulated_changes[i - 1] + min_trips[candidates[0]] - accumulated_changes[candidates[0]] + 2
33          
34            # Remove suboptimal candidates from the end of deque
35            if i < num_boxes:
36                while candidates and min_trips[candidates[-1]] - accumulated_changes[candidates[-1]] >= min_trips[i] - accumulated_changes[i]:
37                    candidates.pop()
38                candidates.append(i)
39      
40        # The last element in min_trips contains the minimum number of trips needed for all boxes
41        return min_trips[num_boxes]
42

Java Solution

1class Solution {
2  
3    // Function to calculate the minimum number of trips to deliver all the boxes.
4    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
5        int numberOfBoxes = boxes.length; // Total number of boxes to deliver.
6      
7        // Initialize array for prefix sums of weights.
8        long[] weightPrefixSums = new long[numberOfBoxes + 1];
9      
10        // Initialize array to count distinct contiguous ports.
11        int[] distinctPorts = new int[numberOfBoxes];
12      
13        // Calculate prefix sums of weights and distinct contiguous ports counts.
14        for (int i = 0; i < numberOfBoxes; ++i) {
15            int port = boxes[i][0]; // Current box's port.
16            int weight = boxes[i][1]; // Current box's weight.
17            weightPrefixSums[i + 1] = weightPrefixSums[i] + weight; // Maintain prefix sum of weights.
18            if (i < numberOfBoxes - 1) {
19                // Count distinct ports by comparing adjacent boxes.
20                distinctPorts[i + 1] = distinctPorts[i] + (port != boxes[i + 1][0] ? 1 : 0);
21            }
22        }
23      
24        // Initialize the dynamic programming array for the minimum number of trips.
25        int[] minTrips = new int[numberOfBoxes + 1];
26      
27        // Use a deque to optimize the dynamic programming approach.
28        Deque<Integer> deque = new ArrayDeque<>();
29        deque.offer(0);
30      
31        // Dynamic programming to calculate minimum number of trips to deliver all boxes.
32        for (int i = 1; i <= numberOfBoxes; ++i) {
33            // While any box violates the maxBoxes or maxWeight constraint, remove from deque.
34            while (!deque.isEmpty() &&
35                (i - deque.peekFirst() > maxBoxes || weightPrefixSums[i] - weightPrefixSums[deque.peekFirst()] > maxWeight)) {
36                deque.pollFirst();
37            }
38          
39            // If deque is not empty, calculate the minimum trips needed.
40            if (!deque.isEmpty()) {
41                minTrips[i] = distinctPorts[i - 1] + minTrips[deque.peekFirst()] - distinctPorts[deque.peekFirst()] + 2;
42            }
43          
44            // Optimize deque to maintain the candidate indexes for dynamic programming.
45            if (i < numberOfBoxes) {
46                while (!deque.isEmpty() && minTrips[deque.peekLast()] - distinctPorts[deque.peekLast()] >= minTrips[i] - distinctPorts[i]) {
47                    deque.pollLast();
48                }
49                deque.offer(i);
50            }
51        }
52        // Result is the minimum number of trips to deliver all boxes.
53        return minTrips[numberOfBoxes];
54    }
55}
56

C++ Solution

1#include <vector>
2#include <deque>
3using namespace std;
4
5class Solution {
6public:
7    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
8        int numBoxes = boxes.size();
9      
10        // Initialize arrays to store cumulative weights, port shifts, and min trips
11        vector<long> cumulativeWeights(numBoxes + 1, 0);
12        vector<int> portShifts(numBoxes, 0);
13        vector<int> minTrips(numBoxes + 1, 0);
14
15        // Pre-compute the cumulative weights and port shifts
16        for (int i = 0; i < numBoxes; ++i) {
17            int port = boxes[i][0], weight = boxes[i][1];
18            cumulativeWeights[i + 1] = cumulativeWeights[i] + weight;
19            // Count the port shifts by comparing consecutive boxes
20            if (i < numBoxes - 1) {
21                portShifts[i + 1] = portShifts[i] + (port != boxes[i + 1][0]);
22            }
23        }
24
25        // Deque to optimize the calculation of minTrips 
26        deque<int> queue{0};
27
28        // Main loop to calculate the minTrips using sliding window technique
29        for (int i = 1; i <= numBoxes; ++i) {
30            // Remove obstacles (exceeding the limits of maxBoxes or maxWeight)
31            while (!queue.empty() && (i - queue.front() > maxBoxes || 
32                  cumulativeWeights[i] - cumulativeWeights[queue.front()] > maxWeight)) {
33                queue.pop_front();
34            }
35          
36            // If not empty, calculate the trips required until this box
37            if (!queue.empty()) {
38                minTrips[i] = portShifts[i - 1] + minTrips[queue.front()] - portShifts[queue.front()] + 2;
39            }
40
41            // Prune the queue by removing obsolete states
42            if (i < numBoxes) {
43                while (!queue.empty() && minTrips[queue.back()] - portShifts[queue.back()] >= minTrips[i] - portShifts[i]) {
44                    queue.pop_back();
45                }
46                queue.push_back(i);
47            }
48        }
49
50        // Answer is the min number of trips to deliver all boxes
51        return minTrips[numBoxes];
52    }
53};
54

Typescript Solution

1type Box = [number, number]; // Type alias to represent a box as a tuple of port number and weight
2
3// Computes the cumulative weights of the boxes
4function computeCumulativeWeights(boxes: Box[]): number[] {
5    const cumulativeWeights: number[] = [0];
6    for (let i = 0; i < boxes.length; ++i) {
7        cumulativeWeights[i + 1] = cumulativeWeights[i] + boxes[i][1];
8    }
9    return cumulativeWeights;
10}
11
12// Computes the number of port shifts between boxes
13function computePortShifts(boxes: Box[]): number[] {
14    const portShifts: number[] = [0];
15    for (let i = 1; i < boxes.length; ++i) {
16        portShifts[i] = portShifts[i - 1] + (boxes[i][0] !== boxes[i - 1][0] ? 1 : 0);
17    }
18    return portShifts;
19}
20
21// Main algorithm to calculate the minimum number of trips required to deliver all boxes
22function boxDelivering(boxes: Box[], portsCount: number, maxBoxes: number, maxWeight: number): number {
23    const numBoxes = boxes.length;
24    const cumulativeWeights = computeCumulativeWeights(boxes);
25    const portShifts = computePortShifts(boxes);
26    const minTrips: number[] = new Array(numBoxes + 1).fill(0);
27    const queue: number[] = [0];
28
29    for (let i = 1; i <= numBoxes; ++i) {
30        // Remove the first box from the deque if it exceeds the limit of maxBoxes or maxWeight
31        while (queue.length > 0 &&
32               (i - queue[0] > maxBoxes || cumulativeWeights[i] - cumulativeWeights[queue[0]] > maxWeight)) {
33            queue.shift();
34        }
35      
36        // Calculate the trips required up to the current box if the deque is not empty
37        if (queue.length > 0) {
38            minTrips[i] = portShifts[i - 1] + minTrips[queue[0]] - portShifts[queue[0]] + 2;
39        }
40
41        // Remove states from the deque that will not be used again because they result in a higher number of trips
42        while (queue.length > 0 && minTrips[i] - portShifts[i] <= minTrips[queue[queue.length - 1]] - portShifts[queue[queue.length - 1]]) {
43            queue.pop();
44        }
45
46        // Add the current index to the deque
47        queue.push(i);
48    }
49
50    // The final entry in the minTrips array is the answer, representing the minimum number of trips
51    return minTrips[numBoxes];
52}
53

Time and Space Complexity

Time Complexity

The given code consists of several parts which contribute to the overall time complexity:

  • Precomputing the cumulative weights ws: This is done using accumulate which iterates over each box once, resulting in a time complexity of O(n) where n is the number of boxes.

  • Precomputing the port switch counter cs: Similarly, accumulate is used along with pairwise to count the number of port switches. Assuming pairwise works in constant time for each pair, this will also have a time complexity of O(n).

  • Filling the dynamic programming array f: The code iterates over each box and updates the f[i] using the information in a double-ended queue q. The while loop inside this iteration can run at most n times in the worst-case scenario, but since each element is pushed to and popped from q at most once, this "amortizes" to O(n) over the entire loop.

  • Maintaining the queue q: Throughout the entire for loop, each element is added once and removed once. The while loop checks for the constraints on maxBoxes and maxWeight and pops elements from the head, and the inner while loop checks for the optimal f values and pops from the tail. Each element is pushed to and popped from q at most once, leading to a complexity of O(n).

From the above analysis, every operation in the main loop has at most a linear relationship with n, making the time complexity of the entire code O(n).

Space Complexity

The space complexity is determined by the space required to store the precomputed sums ws and cs, the dynamic programming table f, and the queue q:

  • The cumulative weight sums ws and port switch counter cs are both O(n) space.

  • The dynamic programming array f is also O(n) space.

  • The queue q can potentially store all n indices in the worst case, leading to O(n) space.

Thus, the overall space complexity of the code is O(n).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫