BinarySearch 0479 Leetcode 1011. Capacity To Ship Packages Within D Days

Problem statement

https://binarysearch.com/problems/Skydivers/

Solution

Equal to Leetcode 1011. Capacity To Ship Packages Within D Days.

Complexity

It is O(n log M) for time and O(n) for space, where M = sum(W).

Code

class Solution:
    def solve(self, W, D):
        def check(x):
            need, cur = 1, 0
            for w in W:
                if cur + w > x:
                    need += 1
                    cur = 0
                cur += w
            return need
        
        beg, end = max(W) - 1, sum(W)
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid) > D:
                beg = mid
            else:
                end = mid
                
        return end