We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Capacity To Ship Packages Within D Days

Difficulty: Medium

Problem Description

Given a list of package weights and a number of days, determine the minimum weight capacity of a ship that can ship all the packages in the given order within the specified number of days.

Key Insights

  • The total weight of packages must be distributed across the specified number of days without exceeding the ship's capacity on any single day.
  • The capacity must be at least equal to the heaviest package to ensure all packages can be shipped.
  • A binary search approach can efficiently find the minimum capacity by testing various capacities and checking if all packages can be shipped within the given days.

Space and Time Complexity

Time Complexity: O(n log m), where n is the number of packages and m is the maximum weight capacity. Space Complexity: O(1), as we are using a fixed amount of space regardless of input size.

Solution

To solve this problem, we can use a binary search approach to find the minimum capacity of the ship. The binary search will range between the maximum weight of a single package (as the lower bound) and the sum of all package weights (as the upper bound). For each mid-point capacity during the search, we will check if it's feasible to ship all packages within the specified number of days. This is done by iterating through the packages and accumulating weights until we reach the capacity, incrementing the day count when the capacity is exceeded.

Code Solutions

def canShip(weights, capacity, days):
    current_weight = 0
    days_needed = 1
    
    for weight in weights:
        if current_weight + weight > capacity:
            days_needed += 1
            current_weight = weight
            if days_needed > days:
                return False
        else:
            current_weight += weight
            
    return True

def shipWithinDays(weights, days):
    left, right = max(weights), sum(weights)
    
    while left < right:
        mid = (left + right) // 2
        if canShip(weights, mid, days):
            right = mid
        else:
            left = mid + 1
            
    return left
← Back to All Questions