LeetCode日本語修行13日目- [1011-全ての荷物がD日以内到着の能力]

Capacity To Ship Packages Within D Days

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

問題の内容:

D日以内にとある港から別の港に出荷するの荷物があります．
i番目の荷物は、weights[i]という重さを持っています。
毎日、荷物を（重さで指定された順に）船に積み込みます。船の最大積載量以上の重さを積んではいけない。
全ての荷物がD日以内到着になる、船の最小積載量は？

例:

例1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation:　Dは:５の時、つまり、船は五回で全部の荷物を送ります。順番は固定です 。船の最小積載量は15。
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

例2:
Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: Dは:３の時、全部の荷物を送ります。順番は固定です。
船の最小積載量は6:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

ヒント:

1 <= D <= weights.length <= 5 * 104
1 <= weights[i] <= 500

この問題は、既定の範囲の中に、一つのvalueを確定です。
範囲とは、
一番左のは、weightsの中に一番重いの荷物です、船の最小積載量はそれより下がると、その荷物を乗らない。。。
一番右のは、全ての荷物の重さです、つまり、D＝１の時、一日で、全部荷物を出荷する事。
weights.max() 〜　weights.sum()から、とあるのvalueを特定する事。
範囲を明確の上、二分探索を使って、解決できる。

    fun shipWithinDays(weights: IntArray, D: Int): Int {
        var left = weights.max() ?: 0
        var right = weights.sum()

        while(left < right){
            var mid = (left + right) / 2
            var needDay = 1
            var curWeight = 0
            for(weight in weights){
                if(curWeight + weight > mid){
                    ++needDay
                    curWeight = 0
                }
                curWeight += weight
            }
            if(needDay <= D){
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }