LC 0410 [H] Split Array Largest Sum - ALawliet/algorithms GitHub Wiki

exact same solution as https://github.com/codewithsenpai/algos/wiki/LC-1011-%5BM%5D-Capacity-To-Ship-Packages-Within-D-Days

class Solution:
    def splitArray(self, weights: List[int], D: int) -> int:
        def big_enough(capacity):
            days = 1
            total = 0
            for weight in weights:
                total += weight
                if total > capacity:
                    total = weight
                    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 - 1
            return l
        
        return binarysearch_left(max(weights), sum(weights))