“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Ability to deliver packages within D days

The title

Parcels on the conveyor belt must be transported from one port to another within days.

The i-th parcel on the conveyor belt is weights[I]. Every day, we load our packages onto the conveyor belt in the order of weights given. The weight we carry will not exceed the maximum carrying weight of the ship.

Returns the minimum carrying capacity of a ship capable of delivering all parcels on the conveyor belt within days.

Example 1

Weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Please note that the goods must be shipped in the given order, so it is not permissible to use a vessel of 14 capacity and divide the packing into (2, 3, 4, 5), (1, 6, 7), (8), (9), (10).Copy the code

Example 2

Enter: weights = [3.2.2.4.1.4], days = 3Output:6Explanation: minimum load of ship6Can be in3Deliver all parcels within days as shown below:1Day:3.2
第 2Day:2.4
第 3Day:1.4

Copy the code

Answer key

dichotomy

Minimum carrying capacity:

  • The lower limit is math. Max (maximum weight of a single package, weight of all packages/days) math. Max (maximum weight of a single package, weight of all packages/days). Assume that the boundary value is leftleftleft
  • The upper limit is the weight of all parcels, assuming that the upper limit is rightrightright

After finding the boundary, we can enumerate the interval [left,right][left,right][left,right] to get the lowest cargo capacity

Note here that the interval [left,right][left,right][left,right] is the increasing interval, and the minimum cargo capacity can be regarded as the target value.

Continuous ordered interval to find the target value, familiar dichotomy;

The important point of the dichotomy is to find the partition condition, in this case, for any amount of cargo KKK

  • If you need more than daydayday to deliver all packages on the conveyor belt, you need to look for [k+1,right][k+1,right][K +1,right]
  • Otherwise, search in the range [left,k][left,k][left,k]

code

var shipWithinDays = function(weights, D) {
    const len = weights.length;
    let max = 0;
    let sum = 0
    for(let i = 0 ; i < len ; i++){
        sum+=weights[i]
        max = Math.max(max,weights[i])
    }
    let left = Math.max(max,Math.ceil(sum/D));
    let right = sum;
    while(left < right){
        let mid = left + Math.floor((right-left)/2)
        if(helper(mid,D)){
           
            right = mid
        }else{
            left = mid+1}}return left;
    function helper(targe,day){
        let num = 0;
        for(let i = 0; i < len ; i++){if(num+weights[i]> targe){
                num = 0;
                day--
            }
            num+=weights[i]
        }
        return day>0}};Copy the code