1687. Delivering Boxes from Storage to Ports
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β, weighti]
, and three integers portsCount
, maxBoxes
, and maxWeight
.
portsββi
is the port where you need to deliver theith
box andweightsi
is the weight of theith
box.portsCount
is the number of ports.maxBoxes
andmaxWeight
are the respective box and weight limits of the ship.
The boxes need to be delivered in the order they are given. The ship will follow these steps:
- The ship will take some number of boxes from the
boxes
queue, not violating themaxBoxes
andmaxWeight
constraints. - For each loaded box in order, the ship will make a trip to the port the box needs to be delivered to and deliver it. If the ship is already at the correct port, no trip is needed, and the box can immediately be delivered.
- The ship then makes a return trip to storage to take more boxes from the queue.
The ship must end at storage after all the boxes have been delivered.
Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.
Example 1:
Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3 Output: 4 Explanation: The optimal strategy is as follows: - The ship takes all the boxes in the queue, goes to port 1, then port 2, then port 1 again, then returns to storage. 4 trips. So the total number of trips is 4. Note that the first and third boxes cannot be delivered together because the boxes need to be delivered in order (i.e. the second box needs to be delivered at port 2 before the third box).
Example 2:
Input: boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6 Output: 6 Explanation: The optimal strategy is as follows: - The ship takes the first box, goes to port 1, then returns to storage. 2 trips. - The ship takes the second, third and fourth boxes, goes to port 3, then returns to storage. 2 trips. - The ship takes the fifth box, goes to port 2, then returns to storage. 2 trips. So the total number of trips is 2 + 2 + 2 = 6.
Example 3:
Input: boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7 Output: 6 Explanation: The optimal strategy is as follows: - The ship takes the first and second boxes, goes to port 1, then returns to storage. 2 trips. - The ship takes the third and fourth boxes, goes to port 2, then returns to storage. 2 trips. - The ship takes the fifth and sixth boxes, goes to port 3, then returns to storage. 2 trips. So the total number of trips is 2 + 2 + 2 = 6.
Constraints:
1 <= boxes.length <= 105
1 <= portsCount, maxBoxes, maxWeight <= 105
1 <= portsββi <= portsCount
1 <= weightsi <= maxWeight
Solutions
Solution 1: Dynamic Programming + Monotonic Queue Optimization
We define $f[i]$ as the minimum number of trips required to transport the first $i$ boxes from the warehouse to the corresponding docks, so the answer is $f[n]$.
The boxes need to be transported in the order of the array. Each time, the truck will take out several consecutive boxes in order, then deliver them to the corresponding docks one by one. After all are delivered, it returns to the warehouse.
Therefore, we can enumerate the index $j$ of the last box transported in the last trip. Then $f[i]$ can be transferred from $f[j]$. During the transfer, we need to consider the following issues:
- When transferring from $f[j]$, the number of boxes on the truck cannot exceed $maxBoxes$
- When transferring from $f[j]$, the total weight of the boxes on the truck cannot exceed $maxWeight$
The state transition equation is:
$$ f[i] = \min_{j \in [i - maxBoxes, i - 1]} \left(f[j] + \sum_{k = j + 1}^i \textit{cost}(k)\right) $$
Where $\sum_{k = j + 1}^i \textit{cost}(k)$ represents the number of trips required to deliver the boxes in $[j+1,..i]$ to their corresponding docks in one trip. This part of the trip count can be quickly calculated using prefix sums.
For example, suppose we take out boxes $1, 2, 3$ and need to deliver them to docks $4, 4, 5$. We first go from the warehouse to dock $4$, then from dock $4$ to dock $5$, and finally from dock $5$ back to the warehouse. It can be seen that it takes $2$ trips to go from the warehouse to the dock and from the dock back to the warehouse. The number of trips from dock to dock depends on whether the two adjacent docks are the same. If they are not the same, the number of trips will increase by $1$, otherwise it remains the same. Therefore, we can calculate the number of trips between docks using prefix sums, and add two trips for the start and end, to calculate the number of trips required to deliver the boxes in $[j+1,..i]$ to their corresponding docks.
The code implementation is as follows:
# 33/39
class Solution:
def boxDelivering(
self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int
) -> int:
n = len(boxes)
ws = list(accumulate((box[1] for box in boxes), initial=0))
c = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]
cs = list(accumulate(c, initial=0))
f = [inf] * (n + 1)
f[0] = 0
for i in range(1, n + 1):
for j in range(max(0, i - maxBoxes), i):
if ws[i] - ws[j] <= maxWeight:
f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2)
return f[n]
// 35/39
class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
long[] ws = new long[n + 1];
int[] cs = new int[n];
for (int i = 0; i < n; ++i) {
int p = boxes[i][0], w = boxes[i][1];
ws[i + 1] = ws[i] + w;
if (i < n - 1) {
cs[i + 1] = cs[i] + (p != boxes[i + 1][0] ? 1 : 0);
}
}
int[] f = new int[n + 1];
Arrays.fill(f, 1 << 30);
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = Math.max(0, i - maxBoxes); j < i; ++j) {
if (ws[i] - ws[j] <= maxWeight) {
f[i] = Math.min(f[i], f[j] + cs[i - 1] - cs[j] + 2);
}
}
}
return f[n];
}
}
// 35/39
class Solution {
public:
int boxDelivering(vector<vector<int>>&