Skip to content

1687. Delivering Boxes from Storage to Ports 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes,
                    int maxWeight) {
    const int n = boxes.size();
    // dp[i] := the minimum trips to deliver boxes[0..i) and return to the
    // storage
    vector<int> dp(n + 1);
    int trips = 2;
    int weight = 0;

    for (int l = 0, r = 0; r < n; ++r) {
      weight += boxes[r][1];

      // The current box is different from the previous one, need to make one
      // more trip.
      if (r > 0 && boxes[r][0] != boxes[r - 1][0])
        ++trips;

      while (r - l + 1 > maxBoxes || weight > maxWeight ||
             // Loading boxes[l] in the previous turn is always no bad than
             // loading it in this turn.
             (l < r && dp[l + 1] == dp[l])) {
        weight -= boxes[l][1];
        if (boxes[l][0] != boxes[l + 1][0])
          --trips;
        ++l;
      }

      //   min trips to deliver boxes[0..r]
      // = min trips to deliver boxes[0..l) + trips to deliver boxes[l..r]
      dp[r + 1] = dp[l] + trips;
    }

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
    final int n = boxes.length;
    // dp[i] := the minimum trips to deliver boxes[0..i) and return to the
    // storage
    int[] dp = new int[n + 1];
    int trips = 2;
    int weight = 0;

    for (int l = 0, r = 0; r < n; ++r) {
      weight += boxes[r][1];

      // The current box is different from the previous one, need to make one
      // more trip.
      if (r > 0 && boxes[r][0] != boxes[r - 1][0])
        ++trips;

      while (r - l + 1 > maxBoxes || weight > maxWeight ||
             // Loading boxes[l] in the previous turn is always no bad than
             // loading it in this turn.
             (l < r && dp[l + 1] == dp[l])) {
        weight -= boxes[l][1];
        if (boxes[l][0] != boxes[l + 1][0])
          --trips;
        ++l;
      }

      //   the minimum trips to deliver boxes[0..r]
      // = the minimum trips to deliver boxes[0..l) +
      //               trips to deliver boxes[l..r]
      dp[r + 1] = dp[l] + trips;
    }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
    n = len(boxes)
    # dp[i] := the minimum trips to deliver boxes[0..i) and return to the
    # storage
    dp = [0] * (n + 1)
    trips = 2
    weight = 0

    l = 0
    for r in range(n):
      weight += boxes[r][1]

      # The current box is different from the previous one, need to make one
      # more trip.
      if r > 0 and boxes[r][0] != boxes[r - 1][0]:
        trips += 1

      # Loading boxes[l] in the previous turn is always no bad than loading it
      # in this turn
      while r - l + 1 > maxBoxes or weight > maxWeight or (l < r and dp[l + 1] == dp[l]):
        weight -= boxes[l][1]
        if boxes[l][0] != boxes[l + 1][0]:
          trips -= 1
        l += 1

      #   min trips to deliver boxes[0..r]
      # = min trips to deliver boxes[0..l) + trips to deliver boxes[l..r]
      dp[r + 1] = dp[l] + trips

    return dp[n]