Capacity To Ship Packages Within D Days | Function to check if the weights can be delivered in D days or not ; Stores the count of days required to ship all the weights if the maximum capacity is mx ; Traverse all the weights ; If total weight is more than the maximum capacity ; If days are more than D , then return false ; Return true for the days < D ; Function to find the least weight capacity of a boat to ship all the weights within D days ; Stores the total weights to be shipped ; Find the sum of weights ; Stores the maximum weight in the array that has to be shipped ; Store the ending value for the search space ; Store the required result ; Perform binary search ; Store the middle value ; If mid can be shipped , then update the result and end value of the search space ; Search for minimum value in the right part ; Print the result ; Driver Code
def isValid ( weight , n , D , mx ) : NEW_LINE INDENT st = 1 NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += weight [ i ] NEW_LINE if ( sum > mx ) : NEW_LINE INDENT st += 1 NEW_LINE sum = weight [ i ] NEW_LINE DEDENT if ( st > D ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def shipWithinDays ( weight , D , n ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += weight [ i ] NEW_LINE DEDENT s = weight [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT s = max ( s , weight [ i ] ) NEW_LINE DEDENT e = sum NEW_LINE res = - 1 NEW_LINE while ( s <= e ) : NEW_LINE INDENT mid = s + ( e - s ) // 2 NEW_LINE if ( isValid ( weight , n , D , mid ) ) : NEW_LINE INDENT res = mid NEW_LINE e = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT s = mid + 1 NEW_LINE DEDENT DEDENT print ( res ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT weight = [ 9 , 8 , 10 ] NEW_LINE D = 3 NEW_LINE N = len ( weight ) NEW_LINE shipWithinDays ( weight , D , N ) NEW_LINE DEDENT