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 i
th box needs to be delivered to, and weight_i
, the weight of the i
th box.
There are three additional constraints provided:
portsCount
, which is the total number of different ports.maxBoxes
, which is the maximum number of boxes the ship can carry during one trip.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.
Learn more about Segment Tree, Queue, Dynamic Programming, Prefix Sum, Monotonic Queue and Heap (Priority Queue) patterns.
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:
-
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 themaxWeight
limit.1ws = list(accumulate((box[1] for box in boxes), initial=0))
Here,
ws[i]
represents the total weight of thei
boxes from the start. -
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 deliveringi
boxes. -
Dynamic Programming Array: An array
f
is initialized with zeros wheref[i]
will eventually hold the minimum number of trips needed to deliver the firsti
boxes.1f = [0] * (n + 1)
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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.
-
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. -
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. -
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 ofcs[1] + f[q[0]] - cs[q[0]] + 2 = 1 + 0 - 0 + 2 = 3
trips fori = 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.
Solution Implementation
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
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
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
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 usingaccumulate
which iterates over each box once, resulting in a time complexity ofO(n)
wheren
is the number of boxes. -
Precomputing the port switch counter
cs
: Similarly,accumulate
is used along withpairwise
to count the number of port switches. Assumingpairwise
works in constant time for each pair, this will also have a time complexity ofO(n)
. -
Filling the dynamic programming array
f
: The code iterates over each box and updates thef[i]
using the information in a double-ended queueq
. The while loop inside this iteration can run at mostn
times in the worst-case scenario, but since each element is pushed to and popped fromq
at most once, this "amortizes" toO(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 onmaxBoxes
andmaxWeight
and pops elements from the head, and the inner while loop checks for the optimalf
values and pops from the tail. Each element is pushed to and popped fromq
at most once, leading to a complexity ofO(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 countercs
are bothO(n)
space. -
The dynamic programming array
f
is alsoO(n)
space. -
The queue
q
can potentially store alln
indices in the worst case, leading toO(n)
space.
Thus, the overall space complexity of the code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.