A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10 Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], days = 4 Output: 3 Explanation: 1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1
Constraints:
1 <= days <= weights.length <= 5 * 10^41 <= weights[i] <= 500
The description was taken from https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/.
#O(Log(N)) Time, O(1) Space where N is length of weights.class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: left, right = max(weights), sum(weights) while left < right: day = 1 load = 0 capacity = (left+right)//2 for weight in weights: load += weight if load > capacity: day += 1 load = weight if day > days: left = capacity + 1 else: right = capacity return leftThe intuition for this one is rough, but this is nearly the same solution as Koko Eating Bananas.
There is no sorted input and we aren't looking for a target value within that input. However, there is a sorted output, and we are looking for a target value within that output.
Those indicate that a binary search may be a good approach.
What we can do is start with a capacity rate in the middle of our output range. If we see that this rate is too slow and took too many days to carry each load, we will try bumping it up. If we see that we were able to carry each load with the current capacity, but maybe by a long shot, we will try slowing it down. We will do this until we find the minimum capacity we need in order to carry each load before we run out of days.
Where should we begin our search?
The minimum number we could possibly need is the greatest load in the weights array. If we had a fifteen-ton load and wanted to carry it all in a single day, we would need a fifteen-ton capacity.
The maximum number we could possibly need is the combined weight of all of the loads in the weights array. If we wanted to carry everything in one trip, we would need a capacity to carry everything.
left, right = max(weights), sum(weights)
Now let's start our search.
Within our search, while the left pointer and right pointers haven't overlapped, that means that we still have capacity values to consider for the minimum, so we will continue the search.
while left < right:
At the beginning of each new capacity that we are considering within each iteration, we will restart at day one.
We will also reset our load counter that will track the running weight sum so we know whether or not we need to start a new day when we've run out of capacity.
day = 1 load = 0
The capacity we choose within each search iteration will be right smack in the middle of our left and right pointers.
capacity = (left+right)//2
Now let's start stacking on these loads.
For each weight from the input array, we will add it to our load.
for weight in weights: load += weight
If the load gets over capacity, we will require a new day to continue loading the weight.
So, we will increment the day by one and start at the same weight we weren't able to put on the day before.
if load > capacity: day += 1 load = weight
After we are done shipping each load, we will look at how many days it took.
If the day counter is greater than the days we have allotted, we will need a bigger capacity, so we will move our lower bound past where our current capacity is.
if day > days: left = capacity + 1
Otherwise, we were able to ship everything within the allotted timeframe, but we should still see if we can do better by moving our search to a lower capacity.
else: right = capacity
Once our pointers overlap, that means we have exhausted the best search spaces to find the minimum value.
We can return either pointer, but this is the minimum capacity we will need to eat in order to finish all of our shipments.
return left