leetcode 1011 .D日以内に出荷する能力

5210 ワード
algorithms javascript テキストリンク

説明
コンベアベルトは、D日以内に別のポートから別のポートに出荷される必要がありますパッケージを持っています.
コンベヤーベルトの上の第thパッケージは、重さ［i］の重さを持ちます.毎日、我々はコンベヤーベルト(重量によって与えられる順序で)でパッケージで船をロードします.我々は、船の最大重量容量より多くの重量をロードすることはできません.
d日以内に出荷されているコンベヤーベルト上のすべてのパッケージに結果として生じる船の最小重量容量を返します.

解決方法
時間複雑性:O(n ^ 2 log(n))
空間の複雑さ: O ( 1 )
   // Binary search approach
var shipWithinDays = function(weights, D) {
    function getDays(capacity) {
        let days = 1, total = 0;

        // See how many days it will take to unload all the weights given the current capacity
        for(let n of weights) {
            total += n;
            // Increase days only when we will exceed the capacity
            if(total > capacity) {
                total = n;
                days++;
            }
        }
        return days;
    }

    // Start is the minimum capacity of one day which is the max of all the weights
    // End is the max capacity we could load on one day which is the sum of all the weights
    let start = Math.max(...weights), 
        end = weights.reduce((acc, cur) => acc + cur, 0);

    // The min cacpaity needed is between start and finish
    while(start < end) {
        const mid = Math.floor((end+start)/2);
        // See how many days it would take to unload all the weigths given mid as the current capacity
        const days = getDays(mid);
        // If capacity at mid took more than D days to load, then we can add more weigth on the ships each day which means we need to increase the daily capacity
        if(days > D) start = mid+1;
        // mid might be our answer so we cannot set end to mid-1
        else end = mid;
    }
    return end;
};
v-auto-disable
JavaScriptの信頼性と虚偽価値