Proficient Level
Implement the shipPackagesWithinDaysCapacity method that returns the minimum ship capacity needed to deliver packages within given days.
You are given package weights in order and a number of days. A ship must load packages in the given order, and the total weight loaded in one day cannot exceed the ship capacity.
Return the minimum capacity required to ship all packages within the given number of days.
Use binary search on the answer.
The minimum possible capacity is the heaviest single package. The maximum possible capacity is the sum of all package weights. For a candidate capacity, simulate loading packages day by day and count how many days are needed.
If the candidate capacity can finish within the allowed days, try a smaller capacity. Otherwise, increase the capacity.
Pseudocode:
function shipPackagesWithinDaysCapacity(weights, size, days):
left = maximum weight
right = sum of all weights
while left < right:
capacity = (left + right) / 2
neededDays = 1
currentLoad = 0
for each weight in weights:
if currentLoad + weight > capacity:
neededDays++
currentLoad = 0
currentLoad += weight
if neededDays <= days:
right = capacity
else:
left = capacity + 1
return left