1011. Capacity To Ship Packages Within D Days

source: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Question

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

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.

暴力法

先算出在本载荷的情况下，需要多少天，然后慢慢相加，找出最小值。

/**
 * 暴力法
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {
    const getDays = (weights, payload) => {
        let total = 0;
        let leftPayload = payload;
        for (let i = 0; i < weights.length; i++) {
            const crrLeftPayload = leftPayload - weights[i];
            // 运力不足
            if (crrLeftPayload < 0) {
                total += 1;
                leftPayload = payload - weights[i];
            } else {
                leftPayload = crrLeftPayload;
            }
        }
        total += 1;
        return total;
    };
    // 载荷不能小于最大重量
    let payload = Math.max(...weights);
    while (true) {
        const total = getDays(weights, payload);
        if (total <= days) return payload;
        payload += 1;
    }
};

二分查找

对于有序数组寻找边界，很容易想到二分查找边界。

比较值得注意的是最大值的取值：是一次性把所有货物都运走的方式，即days的最小值是1的情况。

/**
 * 二分查找
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {
    const getDays = (weights, payload) => {
        let total = 0;
        let leftPayload = payload;
        for (let i = 0; i < weights.length; i++) {
            const crrLeftPayload = leftPayload - weights[i];
            // 运力不足
            if (crrLeftPayload < 0) {
                total += 1;
                leftPayload = payload - weights[i];
            } else {
                leftPayload = crrLeftPayload;
            }
        }
        total += 1;
        return total;
    };
    let left = Math.max(...weights);
    let right = 5 * (10 ** 4) * 500;
    while (left <= right) {
        const mid = ~~((left + right) / 2);
        const total = getDays(weights, mid);
        if (total === days) right = mid - 1;
        else if (total > days) left = mid + 1;
        else right = mid - 1;
    }
    return left;
};

End

先找出暴力法，然后优化出二分查找。

对于用二分查找寻找边界的方法应该非常熟悉。