Capacity To Ship Packages Within D Days

Problem Statement

The objective is to determine the minimum capacity of a ship required to transport all packages placed sequentially on a conveyor belt to another port within a specified number of days. Each package has a predefined weight. The ship can load multiple packages daily but cannot exceed a certain weight capacity. It is mandated that the order of the packages on the conveyor belt is preserved when loading them onto the ship. Therefore, the challenge involves calculating the least weight capacity that would enable the complete transfer of packages within the given timeframe, taking into account the constraints imposed by the package weights and the number of days available for shipment.

Examples

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 * 104
• 1 <= weights[i] <= 500

Approach and Intuition

The problem outlined involves determining the minimal ship capacity to distribute packages over a number of days without violating the sequential order of the weights array. Given the constraints and the necessity to maintain the order of shipment, a greedy or straightforward approach is inefficient. Instead, we turn towards a binary search combined with a checking mechanism that efficiently validates the potential capacity.

Here's how the approach and solution can be conceptualized:

1. Identify the basic boundaries for the binary search:
   • Lower Bound: The maximum value in weights. At minimum, the ship's capacity should be able to carry the heaviest single package.
   • Upper Bound: The sum of all items in weights. This represents the scenario where all packages are shipped in one day.
2. Utilize binary search between these bounds:
   1. Calculate the middle point (mid) which represents a potential ship capacity.
   2. Check if using this capacity can distribute all packages within the given days:
      • Start accumulating weights day-by-day.
      • If adding another package exceeds the mid (current capacity under test), start a new day and continue accumulating from the next package.
      • Keep track of the number of days needed for this capacity.
   3. Based on the number of days calculated:
      • If the days required with mid capacity is less than or equal to days, it implies that it might be possible to reduce the capacity. Hence, adjust the upper bound of the binary search to mid - 1 and repeat.
      • If the days exceed, it signifies that the mid capacity is too small, and therefore, adjust the lower bound to mid + 1.
3. Continue the binary search process until the lower bound exceeds the upper bound. The optimal solution (minimal ship capacity) is found at the lowest mid for which the shipment schedule fits within the days provided.

By employing this precise and logical strategy of binary search and day-by-day capacity checking, we can efficiently find the minimal ship capacity needed to meet the shipment schedule requirement.

Solutions

class Solution {
public:
    bool canShip(vector<int>& weights, int capacity, int maxDays) {
        int requiredDays = 1, totalWeight = 0;
        for (int w : weights) {
            totalWeight += w;
            if (totalWeight > capacity) {
                requiredDays++;
                totalWeight = w;
            }
        }
        return requiredDays <= maxDays;
    }
    
    int shipWithinDays(vector<int>& weights, int days) {
        int minimumLoad = 0, maximumWeight = 0;
        for (int weight : weights) {
            minimumLoad += weight;
            if(weight > maximumWeight) maximumWeight = weight;
        }
    
        int low = maximumWeight, high = minimumLoad;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canShip(weights, mid, days)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
};