Capacity To Ship Packages Within D Days

LeetCode 1011: Capacity To Ship Packages Within D Days Solution & Explanation

Problem Overview

TL;DR: Perform a binary search on the range of possible ship capacities, using a greedy simulation to verify if a specific capacity allows shipping all packages within the deadline.

The problem asks us to determine the minimum ship capacity required to transport a sequence of packages within a specified number of days, days. The packages must be shipped in the order they appear on the conveyor belt. We are given an array weights representing the packages and an integer days. We must return the lowest integer capacity such that the shipping process takes no more than days.

This is a classic optimization problem found in the LeetCode 1011: Capacity To Ship Packages Within D Days challenge. It requires balancing constraints to find an optimal threshold.

Brute Force Approach for Capacity To Ship Packages Within D Days

The brute force approach involves checking every possible ship capacity starting from the smallest valid capacity and increasing it until we find one that satisfies the time constraint.

1. Determine Bounds: The absolute minimum capacity must be equal to the heaviest package (otherwise, that package can never be loaded). The maximum necessary capacity is the sum of all weights (shipping everything in 1 day).
2. Iterate: Start a loop from max(weights) up to sum(weights).
3. Simulate: For each capacity C, simulate the shipping process. Iterate through the weights array, accumulating weight into a "current day." Once the accumulated weight exceeds C, increment the day counter and start a new day.
4. Check: If the total days required is less than or equal to the input days, return C immediately.

Pseudo-code

min_cap = max(weights)
max_cap = sum(weights)

for capacity from min_cap to max_cap:
    days_needed = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            days_needed += 1
            current_load = 0
        current_load += w
    
    if days_needed <= days:
        return capacity

Time Complexity Analysis

The time complexity is $O(N \cdot S)$, where $N$ is the number of packages and $S$ is the sum of all weights (representing the search space size). Since the sum of weights can be significantly larger than $N$ (up to $500 \times 5 \cdot 10^4 = 2.5 \cdot 10^7$), this approach will result in a Time Limit Exceeded (TLE) error. The search space is too large to traverse linearly.

Algorithm Strategy: Binary Search Patterns

We implement the optimal solution using the Binary Search - On Answer pattern.

1. Initialize Pointers: Set left to the maximum element in weights and right to the sum of elements in weights.
2. Binary Search Loop: While left < right:
   • Calculate the midpoint: mid = left + (right - left) / 2.
   • Evaluate feasible(mid).
   • If True: This capacity works. It might be the minimal capacity, or there might be a smaller valid one. We record mid as a potential answer by setting right = mid.
   • If False: This capacity is too small. We need a larger capacity, so we set left = mid + 1.
3. Return Result: When the loop terminates (left == right), left represents the minimum feasible capacity.

The Feasibility Check (Greedy Approach)

To check if a specific capacity works:

• Initialize days_needed = 1 and current_load = 0.
• Iterate through weights.
• Add the current package weight to current_load.
• If current_load exceeds capacity, it means the current package cannot fit in the current day. We must:
  • Increment days_needed.
  • Reset current_load to the weight of the current package (starting a new day).
• If days_needed exceeds the allowed days, return False.
• Otherwise, return True.

Execution Flow

Consider weights = [1, 2, 3, 4, 5], days = 3.

1. Initialization:

   • left = 5 (max weight)
   • right = 15 (sum of weights)

2. Iteration 1:

   • mid = (5 + 15) // 2 = 10.
   • Check feasible(10):
     • Day 1: 1+2+3+4 = 10 (Full).
     • Day 2: 5.
     • Total days: 2. Since 2 <= 3, returns True.
   • Logic: 10 works, try smaller. right = 10.

3. Iteration 2:

   • left = 5, right = 10.
   • mid = (5 + 10) // 2 = 7.
   • Check feasible(7):
     • Day 1: 1+2+3 = 6. (Adding 4 would exceed 7).
     • Day 2: 4. (Adding 5 would exceed 7).
     • Day 3: 5.
     • Total days: 3. Since 3 <= 3, returns True.
   • Logic: 7 works, try smaller. right = 7.

4. Iteration 3:

   • left = 5, right = 7.
   • mid = (5 + 7) // 2 = 6.
   • Check feasible(6):
     • Day 1: 1+2+3 = 6.
     • Day 2: 4.
     • Day 3: 5.
     • Total days: 3. Since 3 <= 3, returns True.
   • Logic: 6 works, try smaller. right = 6.

5. Iteration 4:

   • left = 5, right = 6.
   • mid = (5 + 6) // 2 = 5.
   • Check feasible(5):
     • Day 1: 1+2 = 3. (Adding 3 exceeds 5).
     • Day 2: 3. (Adding 4 exceeds 5).
     • Day 3: 4. (Adding 5 exceeds 5).
     • Day 4: 5.
     • Total days: 4. Since 4 > 3, returns False.
   • Logic: 5 is too small. left = 6.

6. Termination:

   • left is 6, right is 6. Loop ends.
   • Return left (6).

Proof of Correctness

The algorithm relies on the monotonicity of the problem. Let $f(c)$ be a boolean function indicating if capacity $c$ is valid.

1. Invariant: The optimal solution always lies within the interval [left, right].
2. Initialization: We know the answer must be at least max(weights) and at most sum(weights).
3. Maintenance:
   • If mid is valid ($f(mid)$ is true), then mid could be the answer, or the answer is smaller. We reduce the range to [left, mid]. The answer is still in range.
   • If mid is invalid ($f(mid)$ is false), then mid and anything smaller is also invalid. We reduce the range to [mid + 1, right]. The answer is still in range.
4. Termination: The range shrinks by half at each step. When left == right, the search space has converged to the single smallest valid capacity.

Pattern Reuse Notes

The Binary Search on Answer pattern is a powerful technique for optimization problems where the solution space is ordered.

• LeetCode 410: Split Array Largest Sum: Identical logic. Instead of "days", you split into "m subarrays". You minimize the largest sum among these subarrays.
• LeetCode 774: Minimize Max Distance to Gas Station: Uses binary search on floating-point numbers to find the minimum possible penalty (distance).
• LeetCode 875: Koko Eating Bananas: Finds the minimum eating speed (capacity) to finish bananas within h hours.
• LeetCode 1011: Capacity To Ship Packages Within D Days: The problem discussed here.

These problems all share the structure: "Find the minimum value $X$ such that a condition $F(X)$ is true," where $F$ is monotonic.

Reference Implementation

C++ Solution for LeetCode 1011

1#include <vector>
2#include <numeric>
3#include <algorithm>
4
5class Solution {
6public:
7    int shipWithinDays(std::vector<int>& weights, int days) {
8        // Initialize binary search bounds
9        int left = 0;
10        int right = 0;
11        
12        for (int w : weights) {
13            left = std::max(left, w);
14            right += w;
15        }
16
17        while (left < right) {
18            int mid = left + (right - left) / 2;
19            
20            if (canShip(weights, days, mid)) {
21                right = mid; // Try smaller capacity
22            } else {
23                left = mid + 1; // Increase capacity
24            }
25        }
26        
27        return left;
28    }
29
30private:
31    bool canShip(const std::vector<int>& weights, int days, int capacity) {
32        int daysNeeded = 1;
33        int currentLoad = 0;
34        
35        for (int w : weights) {
36            if (currentLoad + w > capacity) {
37                daysNeeded++;
38                currentLoad = 0;
39            }
40            currentLoad += w;
41        }
42        
43        return daysNeeded <= days;
44    }
45};

Java Solution for LeetCode 1011

1class Solution {
2    public int shipWithinDays(int[] weights, int days) {
3        int left = 0;
4        int right = 0;
5        
6        // Determine bounds
7        for (int w : weights) {
8            left = Math.max(left, w);
9            right += w;
10        }
11        
12        while (left < right) {
13            int mid = left + (right - left) / 2;
14            
15            if (canShip(weights, days, mid)) {
16                right = mid; // Feasible, try to minimize
17            } else {
18                left = mid + 1; // Not feasible, increase capacity
19            }
20        }
21        
22        return left;
23    }
24    
25    private boolean canShip(int[] weights, int days, int capacity) {
26        int daysNeeded = 1;
27        int currentLoad = 0;
28        
29        for (int w : weights) {
30            if (currentLoad + w > capacity) {
31                daysNeeded++;
32                currentLoad = 0;
33            }
34            currentLoad += w;
35        }
36        
37        return daysNeeded <= days;
38    }
39}

Python Solution for LeetCode 1011

1class Solution:
2    def shipWithinDays(self, weights: list[int], days: int) -> int:
3        def can_ship(capacity):
4            days_needed = 1
5            current_load = 0
6            for w in weights:
7                if current_load + w > capacity:
8                    days_needed += 1
9                    current_load = 0
10                current_load += w
11            return days_needed <= days
12
13        # Initialize bounds
14        left = max(weights)
15        right = sum(weights)
16
17        while left < right:
18            mid = left + (right - left) // 2
19            if can_ship(mid):
20                right = mid  # Valid capacity, try smaller
21            else:
22                left = mid + 1  # Invalid, need larger capacity
23        
24        return left