Capacity To Ship Packages Within D Days - Leetcode Solution

Problem Statement:

You have a list of n integers costs where costs[i] is the cost of ith item. You want to ship all of the items to someplace within d days.

You have to ship the packages in such a way that you minimize the total cost of shipping all the packages. You are allowed to split the packages between days. If you split the packages between days, the cost of shipping on each day cannot exceed some maximum cost C.

Write a function to determine the minimum possible total cost of shipping all the given packages within d days.

Solution:

We need to find the minimum value of C such that we can ship all the packages within d days. We can apply binary search to find this value. Here is a detailed algorithm:

• Set the lower bound of the binary search to the maximum element in the costs array. This is because we cannot ship any package with a cost higher than this value on any day.
• Set the upper bound of the binary search to the sum of all elements in the costs array. This is because we can ship all the packages in a single day if the maximum cost is equal to the sum of all package costs.
• While the lower bound is less than or equal to the upper bound, do the following:
  • Calculate the mid value of the lower and upper bound.
  • Check if it is possible to ship all the packages using the mid value as the maximum cost per day. We can do this by simulating d days of shipping using greedy approach.
  • If it is possible to ship all the packages, update the upper bound to mid - 1.
  • Otherwise, update the lower bound to mid + 1.
• Return the lower bound as the final answer.

Here is the code implementation for the algorithm in Python:

def shipWithinDays(costs, D):
    # Set lower and upper bounds of binary search
    lo, hi = max(costs), sum(costs)
  
    # Perform binary search
    while lo <= hi:
        mid = (lo + hi) // 2
        cur, nxt = 0, 1
        days = 1
        while nxt <= len(costs) and days <= D:
            # Try to add next package to current day
            if sum(costs[cur:nxt]) <= mid:
                nxt += 1
            # Move to next day
            else:
                cur = nxt
                nxt = cur + 1
                days += 1
  
        # Check if all packages were shipped within D days
        if days <= D:
            hi = mid - 1
        else:
            lo = mid + 1
  
    return lo

The time complexity of the algorithm is O(n log m) where n is the number of packages and m is the range of possible values for the maximum cost per day. The space complexity is O(1) as we are only using constant amount of extra memory.

1