To solve this problem, we need to find the minimum capacity of a ship such that all packages can be shipped within D
days. Since the packages must be shipped in order and cannot be split, the key is to determine how to divide them across D
days while respecting the ship's capacity.
What does 'capacity' mean? It’s the maximum weight the ship can carry in a single day. If a ship has capacity 10, it can carry packages like [4,6] or [5,5], but not [4,7] since 4+7 = 11 exceeds the limit.
We want the smallest such capacity that still allows us to ship all packages in exactly D
or fewer days. To find this efficiently, we can use binary search.
Understanding the Search Range
- The lowest possible capacity is the weight of the heaviest package. For example, if the largest package weighs 10, the ship must at least carry 10.
- The highest possible capacity is the total weight of all packages, meaning we ship everything in one day.
How to Check If a Capacity Works
For any capacity we try, we simulate how many days it would take to ship all packages using that capacity:
- Start with day 1 and a sum = 0
- For each package:
- Add its weight to the sum for the current day
- If the sum exceeds the capacity, increment the day count and reset the sum to that package’s weight
If the total number of days required exceeds D
, it means the capacity is too small. Otherwise, it’s a valid capacity and we try a smaller one to see if we can do better.
What Happens in Special Cases?
- Single package: If there's only one package and one day, capacity equals its weight.
- More days than packages: We can ship one package per day, so the capacity only needs to match the largest package weight.
- Empty array: If there are no packages, no capacity is needed. Return 0.
By using binary search between the lowest and highest possible capacities, and checking how many days each candidate capacity would require, we can efficiently find the minimum ship capacity needed to meet the D
day requirement.