Capacity To Ship Packages Within D Days

Problem Statement:

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

The ith 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

Solution:

• Binary search probably would not come to our mind when we first meet this problem. We might automatically treat weights as search space and then realize we’ve entered a dead end after wasting lots of time.
• In fact, we are looking for the minimal one among all feasible capacities. We dig out the monotonicity of this problem: if we can successfully ship all packages within D days with capacity m, then we can definitely ship them all with any capacity larger than m.

Now we can design a condition function, let’s call it feasible, given an input capacity, it returns whether it’s possible to ship all packages within D days.

This can run in a greedy way:

• If there’s still room for the current package, we put this package onto the conveyor belt, otherwise we wait for the next day to place this package. If the total days needed exceeds D, we return False, otherwise we return True._

• Next, we need to initialize our boundary correctly.

  • Obviously capacity should be at least max(weights), otherwise the conveyor belt couldn’t ship the heaviest package.
  • On the other hand, capacity need not be more thansum(weights), because then we can ship all packages in just one day.

class Solution {
    private boolean feasible(int capacity, int days, int[] weights){
        int day = 1;
        int total = 0;
 
        for(int weight: weights){
            total += weight;
            if(total > capacity){//Capacity for the day exceeded, wait for next day!
                total = weight; //weight to start with on the next day.
                day += 1;
                if(day > days){ //Exceeded the days number of days required to ship all the packages
                    return false;
                }
            }
        }
        return true;
    }
 
    public int shipWithinDays(int[] weights, int days) {
        int maxWeight = Integer.MIN_VALUE;
        int totalWeight = 0;
 
        for(int weight: weights){
            totalWeight += weight;
            maxWeight = Math.max(maxWeight, weight);
        }
 
        //capacity should be atleast maxWeight, otherwise we our ship can't ship the container with max weight
        int left = maxWeight;
        int right = totalWeight;
 
        while(left < right){
            int mid = left + (right - left)/2;
 
            if(feasible(mid, days, weights)){
                right = mid;
            } else{
                left = mid + 1;
            }
        }
 
        return left;
    }
}