Capacity To Ship Packages Within D Days

Solution

Binary Search

from math import ceil
class Solution:    
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def ok(capacity):
            # num days needed
            res = 0
            temp = 0
            for weight in weights:
                if temp + weight <= capacity:
                    temp += weight
                else:
                    res += 1
                    temp = weight
            return res < days

        right = sum(weights)
        left = max(ceil(right/days), max(weights))
        
        # binary search
        while left <= right:
            mid = left + (right - left) // 2
            if ok(mid):
                right = mid - 1
            else:
                left = mid + 1

        # return mid
        return mid if ok(mid) else mid+1