1011. Capacity To Ship Packages Within D Days

Link

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.

Now we've got all we need to apply our binary search template:

    public int shipWithinDays(int[] weights, int D) {
        int left = 0; //min capacity
        int right = 0;
        for( int weight : weights){
            left = Math.max(left, weight);
            right += weight;
        }
        //Arrays.sort(weights); //node the order of weight unable to changed
        //Because the workers ship with packages on the conveyor belt (in the order given by weights).
        while(right > left)
        {
            int mid = left + (right-left)/2;
            
            if(isfeasible(mid, weights,D)){
                right = mid;
            }
            else{
                left = mid+1;
            }
        }
        return left;
    }
    
    public boolean isfeasible(int capacity, int[] weights, int D){
        int day = 1;
        int total = 0;
        for(int weight : weights){
            total += weight;
            if(total > capacity){
                total = weight;
                day++;
            }
            if(day > D){
                return false;
            }
        }
        return true;
    }