Capacity To Ship Packages Within D Days
Medium Binary search on the answer
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Packages must be shipped in the given order, with one ship trip per day. Find the smallest ship capacity that ships everything within the given number of days.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest ship capacity that ships everything, in order, within the days.
Why this works: bigger capacity never needs more days. Binary search between the heaviest package and the total weight, counting days greedily.
Example: [1..10], days 5
capacity 15: [1-5] [6-7] [8] [9] [10] → 5 days ✓capacity 14 needs 6 days ✗ → answer 15
✦Hints open one at a time
↗Approach
Binary search capacity in [max, sum]. Feasible capacities form a suffix, so find the first feasible one.
</>Solution (Java)
class Solution {
public int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = Math.max(lo, w);
hi += w;
}
while (lo < hi) {
int cap = (lo + hi) >>> 1;
if (daysNeeded(weights, cap) <= days) hi = cap;
else lo = cap + 1;
}
return lo;
}
private int daysNeeded(int[] weights, int cap) {
int days = 1, load = 0;
for (int w : weights) {
if (load + w > cap) { // start a new day
days++;
load = 0;
}
load += w;
}
return days;
}
}!Common mistake
Starting the search at 1 — capacities below the heaviest package can never work and break the greedy count.
- Time: O(n log(sum)).
- Space: O(1).