$ cat ./coding/410-split-array-largest-sum.md

────────────────────────────────────────────────────────────

410. Split Array Largest Sum

原題： 1011. Capacity To Ship Packages Within D Days

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        def weighting(capacity):
            total = 1
            acc = 0
            for weight in weights:
                if acc + weight > capacity:
                    acc = weight
                    total += 1
                else:
                    acc += weight
            return total
        
        left = max(weights)
        right = sum(weights) + 1

        while left <= right:
            mid = left + (right - left) // 2
            if weighting(mid) > days:
                left = mid + 1
            else:
                right = mid - 1
        
        return left

$ ls ./coding/ | grep -v 410-split-array-largest-sum