***Capacity To Ship Packages Within D Days (Leetcode 1011)

Similar to Allocate Books

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

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        
        def allocate(weights,maxWeight,days):
            
            currWeight=0
            currDay=1
            for i in range(len(weights)):
                if(weights[i]>maxWeight):
                    return False
                
                if(currWeight+weights[i]>maxWeight):
                    currDay+=1
                    if(currDay>days):
                        return False
                    currWeight=weights[i]
                else:
                    currWeight+=weights[i]
            
            return True
        
        
        def bsearch(weights,l,h):
            if(l<=h):
                mid=(l+h)//2
                if(allocate(weights,mid,days)==True):
                    self.ans=min(self.ans,mid)
                    bsearch(weights,l,mid-1)
                else:
                    bsearch(weights,mid+1,h)
            return self.ans
        
        
        n=len(weights)
        self.ans=float('inf')
        l=max(weights)
        h=sum(weights)
        self.ans=bsearch(weights,l,h)
        return self.ans