1011. Capacity To Ship Packages Within D Days

はじめに

転職も見据えて、LeetCodeをコツコツ解いていくことにした。
解くだけでは定着しそうにないので、格闘したLeetCodeの問題をメモしていく。

問題

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.

指定の日にちで全ての荷物を運ぶのに必要な、最低限の容量を求める。

考えの流れ

条件を整理してみる。
・容量としてあり得るのが、荷物の重さの最大値から荷物の合計の重さの間
・制約条件的にシンプルな全探索は無理

解法に紐づけられないのでヒントを見る
→バイナリーサーチを使えとのこと。
→リスト自体は順序で並んでいない。同整理するか。
→weightsリストではなく、容量のリストをバイナリーサーチするか。
・オーダーは、荷物の数をnとすると最悪でO(n⋅log(sum(weights)−max(weights)))？
・やってみよう。

コード

from typing import List

class Solution:
    def check_avairability(self, days, cap_b, weights):
        w_b = 0  # 現在の船の積載量
        w_d = 1  # 現在の日数（1日目から）

        for weight in weights:
            if w_b + weight <= cap_b:
                w_b += weight 
            else:
                if w_d < days:
                    w_d += 1 
                    w_b = weight  
                else:
                    return False 
        return True  

    def shipWithinDays(self, weights: List[int], days: int) -> int:
        left = max(weights)  
        right = sum(weights)  
        
        while left < right:
            mid = (left + right) // 2  

            if self.check_avairability(days, mid, weights):  # `mid` の容量で運べるか確認
                right = mid
            else:
                left = mid + 1  # 運べないなら、容量を大きく

        return left  # 最小の容量が left に収束

まとめ

・バイナリーサーチに帰着できなかった
・何かソートされた配列の大小を比較していくようなときにはバイナリーサーチを思い浮かべるようにしたい
・最初DP？と思ったけど、どう実現するのかわからずやめた
・バイナリサーチのleft,rightをmidからどう定義するかもふわふわしているので要復習