A conveyor belt has packages that must be shipped from one port to another within days days.

The i<sup>th</sup> 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^4
• 1 <= weights[i] <= 500

Least Weight Capacity

Problem Description

We are given an array weights representing the weights of packages on a conveyor belt. We need to ship these packages from one port to another within days days. The packages must be shipped in the order they appear in the weights array. We are looking for the least weight capacity of the ship that will allow us to ship all packages within the given number of days.

Naive Solution

A naive solution would be to try all possible weight capacities from the maximum weight of a single package to the sum of all weights. For each capacity, we simulate the shipping process and check if it can be done within the given number of days. This approach is inefficient because it involves iterating through a large range of possible capacities.

Optimal Solution

We can use binary search to find the least weight capacity. The lower bound of the search space is the maximum weight of a single package, and the upper bound is the sum of all weights. For each capacity in the binary search, we simulate the shipping process and check if it can be done within the given number of days. If it can be done, we try a smaller capacity; otherwise, we try a larger capacity.

def ship_within_days(weights, days):
    def possible(capacity):
        day_count = 1
        current_weight = 0
        for weight in weights:
            if current_weight + weight <= capacity:
                current_weight += weight
            else:
                day_count += 1
                current_weight = weight
                if current_weight > capacity:
                    return False
        return day_count <= days

    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if possible(mid):
            right = mid
        else:
            left = mid + 1
    return left

Example Usage:

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5
result = ship_within_days(weights, days)
print(result)  # Output: 15

weights = [3, 2, 2, 4, 1, 4]
days = 3
result = ship_within_days(weights, days)
print(result)  # Output: 6

weights = [1, 2, 3, 1, 1]
days = 4
result = ship_within_days(weights, days)
print(result)  # Output: 3

Big(O) Run-time Analysis

The binary search runs in O(log(sum(weights) - max(weights))) time. For each capacity in the binary search, we iterate through the weights array once, which takes O(n) time, where n is the number of weights. Therefore, the overall run-time complexity is O(n * log(sum(weights) - max(weights))), where n is the length of the weights array.

Big(O) Space Usage Analysis

The space complexity is O(1) because we are only using a constant amount of extra space for variables like left, right, mid, day_count, and current_weight.

Edge Cases

1. Empty weights array: If the weights array is empty, the function should return 0 (or handle it based on the problem's specific requirements). The code assumes the array will not be empty, as per the constraints.
2. days is greater than or equal to the number of packages: In this case, the minimum capacity is simply the maximum weight of a single package. The algorithm handles this case correctly.
3. A single package weight exceeds the total allowed weight: The possible function checks if any single package exceeds the current capacity and returns False if it does, ensuring the binary search adjusts accordingly.
4. All packages can be shipped in one day: The binary search will converge to the minimum capacity required to ship all packages in one day if days is large enough. The algorithm handles this case correctly.