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.

Example 1
Input:
weights (int[]) = [1,2,3,4,5,6,7,8,9,10]
size (int) = 10
days (int) = 5
Return:
(int) 15
Example 2
Input:
weights (int[]) = [3,2,2,4,1,4]
size (int) = 6
days (int) = 3
Return:
(int) 6
Example 3
Input:
weights (int[]) = [1,2,3,1,1]
size (int) = 5
days (int) = 4
Return:
(int) 3

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
Run your code to see the result.