Problem Statement

A conveyor belt has packages that must be shipped in order. You are given an array weights where weights[i] is the weight of the ith package on the conveyor belt. You are also given an integer days, representing the number of days within which all packages must be shipped.

The task is to find the minimum capacity of the conveyor belt such that all the packages can be shipped within days days.

• Each day, the conveyor belt can carry packages whose total weight does not exceed its capacity.
• After delivering the packages on that day, the conveyor belt will be emptied for the next day.
• The packages must be shipped in the order given by weights.

Input

• An array weights, representing the weights of the packages.
• An integer days, the maximum number of days to ship all packages.

Output

• The minimum capacity of the conveyor belt to ship all packages within days.

Examples

Example 1:

Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Output: 15

Explanation: 
The minimum capacity of the conveyor belt is 15.

Day 1: Ship [1, 2, 3, 4, 5] (Total = 15)
Day 2: Ship [6] (Total = 6)
Day 3: Ship [7] (Total = 7)
Day 4: Ship [8] (Total = 8)
Day 5: Ship [9, 10] (Total = 19)

Example 2:

Input: weights = [3, 2, 2, 4, 1, 4], days = 3
Output: 6

Explanation:
The minimum capacity of the conveyor belt is 6.

Day 1: Ship [3, 2] (Total = 5)
Day 2: Ship [2, 4] (Total = 6)
Day 3: Ship [1, 4] (Total = 5)

Example 3:

Input: weights = [1, 2, 3, 1, 1], days = 4
Output: 3

Explanation:
The minimum capacity of the conveyor belt is 3.

Day 1: Ship [1, 2] (Total = 3)
Day 2: Ship [3] (Total = 3)
Day 3: Ship [1] (Total = 1)
Day 4: Ship [1] (Total = 1)

Different Approaches

1️⃣ Binary Search

Intuition:

The minimum capacity must be at least the weight of the heaviest package because the conveyer belt has to carry it.

So the low would be the maximum element of the arrays.

The maximum capacity can be sum of all weights, meaning the conveyer belt carries all packages in one day.

So the high would be sum of all elements of the array.

Feasibility Check: For a given conveyer belt capacity, we check if it is possible to ship all packages within D days. This can be done by simulating how many days are needed using the given capacity.

Observation:

• Minimum ship capacity: The minimum ship capacity should be the maximum value in the given array. Let’s understand using an example. Assume the given weights array is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and the ship capacity is 8. Now in the question, it is clearly stated that the loaded weights in the ship must not exceed the maximum weight capacity of the ship. For this constraint, we can never ship the weights 9 and 10, if the ship capacity is 8. That is why, in order to ship all the weights, the minimum ship capacity should be equal to the maximum of the weights array i.e. max(weights[]).
• Maximum capacity: If the ship capacity is equal to the sum of all the weights, we can ship all goods within a single day. Any capacity greater than this will yield the same result. So, the maximum capacity will be the summation of all the weights i.e. sum(weights[]).

Approach:

1. Define the Problem as a Feasibility Check:
   • Simulate if a given conveyer belt capacity to allows us to ship all packages within D days.
2. Apply Binary Search:
   • Use binary search on the range [minCapacity, maxCapacity].
   • For each mid point (capacity), check if it's feasible using the feasibility check.
   • Adjust the range based on the result:
     • If feasible, try a smaller capacity.
     • If not feasible, increase the capacity.

Dry Run:

Code:

#include <iostream>
#include <vector>
#include <numeric> // for accumulate
#include <algorithm> // for max_element

using namespace std;

// Feasibility function to check if capacity works within D days
bool canShip(const vector<int>& weights, int capacity, int D) {
    int days = 1; // Start with 1 day
    int currentLoad = 0;

    for (int weight : weights) {
        if (currentLoad + weight > capacity) {
            // Start a new day
            days++;
            currentLoad = weight;
            if (days > D) return false; // Exceeded the number of days
        } else {
            currentLoad += weight;
        }
    }
    return true;
}

// Main function to find the minimum capacity
int shipWithinDays(vector<int>& weights, int D) {
    int left = *max_element(weights.begin(), weights.end()); // Min capacity
    int right = accumulate(weights.begin(), weights.end(), 0); // Max capacity
    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (canShip(weights, mid, D)) {
            result = mid; // Store the feasible capacity
            right = mid - 1; // Try for a smaller capacity
        } else {
            left = mid + 1; // Increase capacity
        }
    }

    return result;
}

int main() {
    vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int D = 5;
    cout << "Minimum Capacity: " << shipWithinDays(weights, D) << endl;
    return 0;
}

OR:

class Solution {
public:
    // Helper function to calculate the number of days required to ship all packages
    // if the ship's capacity is limited to `limit`.
    int checkDays(vector<int>& weights, int limit) {
        int count = 1;  // Start with at least one day.
        int sum = 0;    // Current weight sum for the current day.

        for (int i = 0; i < weights.size(); i++) {
            // If adding the current package doesn't exceed the limit, add it to the current day.
            if (sum + weights[i] <= limit) {
                sum += weights[i];
            } else {
                // Otherwise, start a new day and reset the sum to the current package weight.
                sum = weights[i];
                count++;  // Increment the day count.
            }
        }

        return count;  // Return the total number of days required for this capacity.
    }

    // Main function to find the minimum ship capacity to ship all packages within `days`.
    int shipWithinDays(vector<int>& weights, int days) {
        int maxi = INT_MIN;  // To find the maximum weight in the array.
        int sum = 0;         // To calculate the total weight of all packages.

        // Step 1: Find the range of the binary search.
        for (int i = 0; i < weights.size(); i++) {
            maxi = max(maxi, weights[i]);  // Find the heaviest package.
            sum += weights[i];            // Calculate the total weight.
        }

        int left = maxi;   // The minimum capacity is the weight of the heaviest package.
        int right = sum;   // The maximum capacity is the sum of all weights.

        // Step 2: Perform binary search to find the minimum capacity.
        while (left <= right) {
            int mid = left + (right - left) / 2;  // Midpoint of the current search range.

            // Check if the current capacity `mid` allows shipping within `days`.
            if (checkDays(weights, mid) <= days) {
                // If it does, try a smaller capacity (move left).
                right = mid - 1;
            } else {
                // Otherwise, increase the capacity (move right).
                left = mid + 1;
            }
        }

        // Step 3: The answer is the smallest capacity found (left).
        return left;
    }
};

Complexity Analysis:

• Time Complexity: O(n log( sum(weights[]) - max(weights[]) )
  • where sum(weights[]) = summation of all the weights, max(weights[]) = maximum of all the weights, n = size of the weights array.
  • We are applying binary search on the range [max(weights[]), sum(weights[])].
• Space Complexity: O(1)