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 allows us to ship the packages in 5 days like this: Day 1: 1, 2, 3, 4, 5 (Total 15) Day 2: 6, 7 (Total 13) Day 3: 8 (Total 8) Day 4: 9 (Total 9) Day 5: 10 (Total 10) Any smaller capacity would force us to take more than 5 days.
Example 2
Input: weights = [3, 2, 2, 4, 1, 4], days = 3
Output: 6
Explanation: A ship capacity of 6 allows us to ship the packages in exactly 3 days: Day 1: 3, 2 (Total 5) Day 2: 2, 4 (Total 6) Day 3: 1, 4 (Total 5)
Brute Force Approach
The ship capacity cannot be smaller than the heaviest package. If the ship cannot carry the heaviest package, that package can never be shipped. The ship capacity also never needs to be bigger than the sum of all package weights. With that much capacity, all packages can be shipped in one day.
So the answer must lie somewhere between: max(weights) and sum(weights)
The simple idea is to try every capacity in this range. For each capacity, simulate the shipping process from left to right and count how many days are needed.
The first capacity that uses at most days days is the answer, because capacities are checked from small to large.
Algorithm
Find the heaviest package and the total weight of all packages. The heaviest package becomes the smallest possible capacity, and the total weight becomes the largest possible capacity.
Try every capacity from the smallest possible value to the largest possible value. This is done because the first valid capacity in this increasing order will be the minimum answer.
For each capacity, scan the packages from left to right. Keep adding packages to the current day while the total does not cross the capacity.
If adding the next package would exceed the capacity, start a new day and place that package in the new day's load. This preserves the original package order.
If the number of days used is at most the allowed
days, return the current capacity.
Key Points
The lower bound is
max(weights)because every package must fit on the ship.The upper bound is
sum(weights)because that capacity can ship everything in one day.
Dry Run
Capacity to Ship Packages within D days Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Counts how many days are needed to ship all packages with the given capacity. */ int daysNeeded(vector<int>& weights, int capacity) { // At least one day is needed when packages exist. int days = 1; // This stores the total weight loaded on the current day. int currentLoad = 0; for (int weight : weights) { // Start a new day when the next package // would cross the ship capacity. if (currentLoad + weight > capacity) { days++; // The current package becomes the first package // loaded on the new day. currentLoad = weight; } else { // The package fits in the current day, // so it can be added to the ongoing load. currentLoad += weight; } } return days; } /* Returns the minimum ship capacity needed to ship all packages within the given days. */ int shipWithinDays(vector<int>& weights, int days) { // The ship must at least carry the heaviest package. int minCapacity = *max_element(weights.begin(), weights.end()); // Carrying all packages in one day is always enough. int maxCapacity = accumulate(weights.begin(), weights.end(), 0); for (int capacity = minCapacity; capacity <= maxCapacity; capacity++) { // The first capacity that finishes within days // is the minimum because capacities increase by one. if (daysNeeded(weights, capacity) <= days) { return capacity; } } return -1; }};// Driver code startsint main() { vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int days = 5; Solution obj; cout << obj.shipWithinDays(weights, days) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x (Sum - Max + 1)), where N is the length of array, Sum is the sum of all elements and Max is the maximum of all the elements. This is because every capacity in the range (Sum - Max + 1) may scan all N packages.
Space Complexity: O(1) , because constant space is used.
Optimal Approach
The useful observation is about what happens when ship capacity increases. If a capacity C can ship all packages within D days, then any capacity larger than C can also do it. A larger ship can carry at least the same packages each day, maybe even more. If a capacity is too small, all smaller capacities are also too small.
So the capacities form a clear pattern: not possible, not possible, possible, possible, possible
The answer is the first possible capacity. That is exactly where binary search on answer helps. Instead of testing every capacity, test the middle capacity and decide whether to move left or right.
The check for one capacity is greedy: keep loading packages in order until the next package would overflow the ship, then start a new day.
Algorithm
Find the search range first. The lower bound is the heaviest package because every package must fit individually. The upper bound is the sum of all weights because that capacity can ship everything in one day.
For a chosen middle capacity, simulate shipping from left to right. This simulation is needed because packages must keep their original order.
During simulation, keep the current day's load. If adding the next package crosses the capacity, increase the day count and start a new day's load with that package.
If the number of needed days is less than or equal to the allowed days, the capacity works. Store it as a possible answer and search left because a smaller working capacity may exist.
If the number of needed days is greater than the allowed days, the capacity is too small. Search right because more capacity is needed.
When binary search finishes, return the best capacity found.
Key Points
days == 1makes the answer equal to the sum of all weights.days == weights.lengthmakes the answer equal to the heaviest package.
Dry Run
Capacity to Ship Packages within D days Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Checks if all packages can be shipped within days using the given capacity. */ bool canShip(vector<int>& weights, int days, int capacity) { // At least one day is needed when packages exist. int usedDays = 1; // This stores the total weight loaded on the current day. int currentLoad = 0; for (int weight : weights) { // Start a new day when the next package // would cross the ship capacity. if (currentLoad + weight > capacity) { usedDays++; // The current package begins the next day // because package order cannot be changed. currentLoad = weight; } else { // The package fits today, so keep it // in the current day's load. currentLoad += weight; } } // This capacity works if shipping finishes // within the allowed number of days. return usedDays <= days; } /* Returns the minimum ship capacity needed using binary search on possible capacities. */ int shipWithinDays(vector<int>& weights, int days) { // The ship must at least carry the heaviest package. int low = *max_element(weights.begin(), weights.end()); // Carrying all packages in one day is always enough. int high = accumulate(weights.begin(), weights.end(), 0); // This stores the smallest valid capacity found so far. int answer = high; while (low <= high) { // mid is the capacity currently being tested. int mid = low + (high - low) / 2; // If mid works, try to find an even smaller valid capacity. if (canShip(weights, days, mid)) { answer = mid; high = mid - 1; } else { // If mid does not work, more capacity is required. low = mid + 1; } } return answer; }};// Driver code startsint main() { vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int days = 5; Solution obj; cout << obj.shipWithinDays(weights, days) << endl; return 0;}Complexity Analysis
Time Complexity: O(N x log2(Sum - Max + 1)), where N is the length of array, because each binary-search check scans all packages once and the binary search has a range of Sum-Max+1 because our ship should at least be able to ship the maximum weight and an upper bound of the sum of all weights gives the range as Sum-Max+1.
Space Complexity: O(1), Because constant space is used
Interview follow-up Questions
If a ship's capacity is strictly less than the heaviest package, it will be impossible to load that specific package, no matter how many days you have. A valid ship must be able to hold the largest single item.
Be the first to add a comment.