1011. Capacity To Ship Packages Within D Days.md

1011. Capacity To Ship Packages Within D Days (Medium)

• binary search for capacity,
• range: max(weights), sum(all weights)
• (lower bound needs to be the max single weight, otherwise, it will never finish.)
• target: minimum capacity that can finish in target days
• if calculated days to finish is too fast or equal, decrease capacity,
• else, increase capacity.

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        ##### lower bound needs to be the max single weight, 
        ## otherwise, it will never finish.
        left, right = max(weights), sum(weights)
        while(left <= right):
            mid = left + (right - left) // 2
            # print(f'{mid}, {self.calculate_days(weights, mid)}')
            if self.calculate_days(weights, mid) <= days:
                temp_capacity = mid
                right = mid - 1
            else:
                left = mid + 1
        return temp_capacity
    def calculate_days(self, weights, capacity):
        weight_sum = 0
        days = 1
        for one in weights:
            weight_sum += one
            if weight_sum > capacity:
                days += 1
                weight_sum = one
        return days