A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10 Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], days = 4 Output: 3 Explanation: 1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1
Constraints:
1 <= days <= weights.length <= 5 * 1041 <= weights[i] <= 500The key idea in #1011 Capacity To Ship Packages Within D Days is to determine the minimum ship capacity that allows all packages to be shipped within the given number of days. Since packages must be shipped in order, we cannot rearrange them, which makes greedy simulation useful.
A common strategy is to apply Binary Search on the answer. The minimum possible capacity is the maximum weight in the array, while the maximum capacity is the sum of all weights. For any candidate capacity, we simulate loading packages day by day and count how many days are required.
If the required days exceed D, the capacity is too small, so we increase it. Otherwise, we try a smaller capacity to minimize the result. This combination of binary search and greedy validation efficiently finds the smallest feasible capacity.
The overall solution runs in O(n log S) time, where S is the sum of weights, and uses O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Greedy Simulation | O(n log S) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Binary search on the answer. We need a function possible(capacity) which returns true if and only if we can do the task in D days.
This approach utilizes a binary search to find the minimal ship capacity that can carry all packages within the specified number of days. The binary search operates over the range from the maximum value in the weights array to the sum of all weights, which are the logical lower and upper bounds for the ship capacity.
Time Complexity: O(n log m), where n is the number of packages and m is the range of the binary search (sum of weights - max weight).
Space Complexity: O(1), as we use constant extra space.
1#include <stdio.h>
2
3int canShip(int weights[], int size, int days, int capacity) {
4 int total =
In this C solution, we define a helper function canShip which checks if a given capacity can ship all packages within the specified days. We use binary search in the shipWithinDays function to find the minimal capacity required, by adjusting the search bounds based on the feasibility determined by canShip.
This approach involves greedy simulation to estimate the minimum capacity by incrementing from the largest single package weight until you find a capacity that can ship all the packages within the days. Note that this approach may take more time in the worst case due to the linear increment.
Time Complexity: O(n * C/m), where C/m is the number of increments in the worst case.
Space Complexity: O(1).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary search is used because the answer space (possible ship capacities) is ordered. If a certain capacity can ship packages within D days, any larger capacity will also work. This monotonic property makes binary search efficient for finding the minimum valid capacity.
Yes, this problem is commonly asked in technical interviews, including FAANG-style companies. It tests understanding of binary search on answer space, greedy validation, and efficient problem modeling.
The problem mainly uses arrays and simple variables for simulation. No advanced data structures are required because packages are processed sequentially while counting the number of days needed for a given capacity.
The optimal approach uses binary search on the possible ship capacity. For each candidate capacity, we simulate loading packages in order and count how many days it takes. This greedy check helps determine whether to increase or decrease the capacity.
This C solution incrementally increases the capacity from the maximum package weight. With each increment, we check if the current capacity is sufficient to ship within the given days using canShip. This approach may take longer due to its linear simulation nature.