LC 1011 [M] Capacity To Ship Packages Within D Days - ALawliet/algorithms GitHub Wiki
like first bad version with leftmost binary search except you come up with the condition for big_enough(m)
and pay attention to the search space l, r = max(weights), sum(weights)
ship packages within D
days
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
def big_enough(capacity):
days = 1
total = 0
for w in weights:
total += w
if total > capacity:
total = w # set to the last weight that we couldn't fit for the first item in the next container
days += 1
if days > D:
return False
return True
def binarysearch_left(l, r):
# l = min search space is the biggest single weight because we need to ship it
# r = max search space is the total weight if we needed the biggest bag possible
while l < r:
m = (l + r) // 2
if not big_enough(m):
l = m + 1
else:
r = m
return l
l = max(weights)
r = sum(weights)
return binarysearch_left(l, r)