Problem statement

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Solution

We need to use binary search + greedy idea, where check(x) is answer for the question how many days we need if we have capacity x.

Complexity

Time complxtiy is O(n log M), where M = sum(W), space complexity is O(n).

Code

class Solution:
    def shipWithinDays(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