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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Capacity To Ship Packages Within D Days

Number: 1056

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Agoda, Bloomberg, DP world, Zeta, TikTok, Apple, Oracle, Mindtickle, Salesforce, Flipkart, Goldman Sachs, Expedia, Uber, Microsoft

Problem Description

Given an array of package weights and an integer D representing the number of days, determine the minimum ship capacity required so that all packages can be shipped within D days. Packages must be loaded in the given order and the ship cannot exceed its capacity on any day.

Key Insights

  • The minimal possible capacity is the maximum value in weights; no ship can carry a package heavier than its capacity.
  • The maximum possible capacity is the sum of all weights; this allows shipping all packages in one day.
  • The problem is monotonic: if a capacity C works, any capacity greater than C will also work.
  • Use binary search on the capacity range and a greedy approach to simulate shipping for each candidate capacity.

Space and Time Complexity

Time Complexity: O(n * log(sum(weights))) where n is the number of packages. Space Complexity: O(1) additional space.

Solution

The solution employs binary search to find the minimum ship capacity. Start by setting the search bounds: the lower bound is the maximum weight (since each package must be shipped individually if needed) and the upper bound is the sum of all weights (shipping everything in one go). For each midpoint capacity in the binary search, use a greedy method to simulate the shipping process—accumulating weights until adding another package would exceed the candidate ship capacity, at which point you increment the day count. If the number of days required exceeds D, the capacity is insufficient and the lower bound is increased; otherwise, adjust the upper bound. Continue until the bounds converge.

Code Solutions

def shipWithinDays(weights, days):
    # Helper function to determine if a given capacity can ship packages within 'days' days.
    def canShip(capacity):
        current_load = 0  # Current total weight on the ship for the current day.
        required_days = 1  # Start with the first day.
        for weight in weights:
            # If adding the current weight exceeds capacity, increment the day counter.
            if current_load + weight > capacity:
                required_days += 1
                current_load = 0
            current_load += weight
        return required_days <= days

    # Establish lower and upper bounds for binary search.
    low, high = max(weights), sum(weights)
    while low < high:
        mid = (low + high) // 2
        # If mid capacity can ship all packages within the allowed days, try a lower capacity.
        if canShip(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Example usage:
weights = [1,2,3,4,5,6,7,8,9,10]
days = 5
print(shipWithinDays(weights, days))
← Back to All Questions