Leetcode 1011. Capacity To Ship Packages Within D Days

Problem Explanation

In this problem, we are given a list of weights representing packages on a conveyor belt that must be shipped from one port to another within a certain number of days. The packages have to be loaded on to the ship with a certain capacity that we're trying to determine. Finding this least weight capacity of the ship that will result in all the packages being shipped within the specified number of days is our goal.

Let's walk through an example:

For instance, given an input where weights = [1,2,3,4,5,6,7,8,9,10], D = 5. The output should be 15. Because with ship capacity of 15 we can load the packages within 5 days like this : 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10

Packages must be shipped in the order given, so splitting the packages into different parts is not allowed.

Now, let's have a look at the solution we have:

The solution is to use a binary search to search for the optimum ship capacity which is in the range of the maximum weight to the sum of all weights. Then we calculate the number of days it would take to ship all the packages with that ship capacity. If the number of days is less than or equal to the given number of days, we reduce the ship capacity; otherwise, we increase the ship capacity. The search continues until we find the smallest ship capacity that can ship all packages within the given number of days.

Solution Approach

The approach is to apply a binary search where the search space is the ship capacity. That's because if we can ship all the packages within the given number of days with a certain ship capacity, then we can also do it with any larger capacity. So we're interested in the minimum ship capacity that can do it, as this is our target.

The low boundary of the search space is the maximum possible weight (worst-case scenario, the ship can at least carry the heaviest package) and the high boundary is the sum of all weights as ship capacity (best-case scenario, the ship can carry all the packages together). The binary search would give us the minimum ship capacity by narrowing our search space.

During the search, for a certain ship capacity, we iterate over the weights and accumulate the sum until it exceeds the current ship capacity. This implies a new day of shipping. If the total number of days is greater than D, the capacity is too small. If it is less or equal to D, the capacity might be the minimal one that does the job, so we keep it in mind and continue our search.

Solution in Python

Below is the solution using Python:

1
2python
3class Solution:
4    def shipWithinDays(self, weights: List[int], days: int) -> int:
5        def can_ship(capacity):
6            total = cur = 0
7            for weight in weights:
8                if cur + weight > capacity:
9                    total += 1
10                    cur = weight
11                else:
12                    cur += weight
13            return total < D 
14
15        left, right = max(weights), sum(weights)
16        while left < right:
17            mid = left + (right-left)//2
18            if can_ship(mid):
19                right = mid
20            else:
21                left = mid + 1
22        return left

Solution in Java

Below is the solution using Java:

1
2java
3class Solution {
4    public int shipWithinDays(int[] weights, int D) {
5        int l = 0, r = 0;
6        for(int w: weights){
7            l = Math.max(l, w);
8            r += w;
9        }
10
11        while(l < r){
12            int m = (l + r) / 2;
13            if(canShip(weights, D, m)) r = m;
14            else l = m + 1;
15        }
16        return l;
17    }
18
19    private boolean canShip(int[] weights, int D, int capacity){
20        int curWeight = 0;
21        for(int i = 0; i < weights.length; ){
22            if(curWeight + weights[i] > capacity){
23                curWeight = 0;
24                D--;
25            } else {
26                curWeight += weights[i];
27                i++;
28            }
29        }
30        return D > 0;
31    }
32}

Solution in Javascript

Below is the solution using Javascript:

1
2javascript
3var shipWithinDays = function(weights, D) {
4    let l = Math.max(...weights);
5    let r = weights.reduce((a,b) => a + b);
6    while (l < r) {
7        let m = Math.floor((l+r)/2);
8        let days = 1;
9        let capacity = 0;
10        for(let weight of weights){
11            if(capacity + weight > m){
12                days++;
13                capacity = weight;
14            }else{
15                capacity += weight;
16            }
17        }
18        if(days <= D){
19            r = m;
20        }else{
21            l = m + 1;
22        }
23    }
24    return l;
25};

Solution in C++

Below is the solution using C++:

1
2c++
3class Solution {
4public:
5    int shipWithinDays(vector<int>& weights, int D) {
6        int l = *max_element(begin(weights), end(weights));
7        int r = accumulate(begin(weights), end(weights), 0);
8        while (l < r) {
9            int m = (l + r) / 2;
10            if (shipDays(weights, m) <= D){
11                r = m;
12            } else{
13                l = m + 1;
14            }
15        }
16        return l;
17    }
18private:
19    int shipDays(const vector<int>& weights, int shipCapacity) {
20        int days = 1;
21        int capacity = 0;
22        for (const int weight : weights){
23            if (capacity + weight > shipCapacity) {
24                ++days;
25                capacity = weight;
26            } else {
27                capacity += weight;
28            }
29        }
30        return days;
31    }
32};

Solution in C#

1
2csharp
3public class Solution {
4    public int ShipWithinDays(int[] weights, int D) {
5        int lo = weights.Max();
6        int hi = lo + weights.Sum();
7        while (lo < hi) {
8            int mid = lo + (hi - lo) / 2;
9            int cur = 0, day = 1;
10            foreach (int w in weights) {
11                if (cur + w > mid) {
12                    cur = 0;
13                    day++;
14                }
15                cur += w;
16            }
17            if (day > D)
18                lo = mid + 1;
19            else
20                hi = mid;
21        }
22        return lo;
23    }
24}

As shown in the code, we continue narrowing the search space by comparing the days needed to ship all the packages with the given number of days. If the days needed are more, we move the left pointer to the right, else we move the right pointer to the left. We repeat this process until the left and right pointers meet, at which point we have found the smallest ship capacity that can ship all packages within the given number of days.## Conclusion

In this problem, we've discussed how to determine the least weight capacity of the ship that will result in all the packages being shipped within a specified number of days. By using the binary search method, we can minimize the searching range from the maximum weight to the sum of all weights. This approach is not only effective but also optimizes the performance to make it run faster.

We've demonstrated this approach in Python, JavaScript, Java, C++ and C#. The core concept is the same for each language: finding the minimum ship capacity by iteratively applying the binary search method and checking if the calculated shipping days are less than or equal to the given limit.

Looking at the solutions across multiple languages not only provides deeper insight into the problem-solving strategy but also illustrates the versatility of the binary search algorithm, a fundamental tool in computer science.

Overall, this problem not only tests the candidate's logic skills and programming skills, but also the ability to implement optimization techniques using binary search. So, this will be a good problem for technical interviews or coding tests to evaluate the candidate’s critical thinking, problem-solving skills and the understanding of binary search algorithms.