class Solution:
def shipWithinDays(self, weights, D):
def canShip(capacity):
days = 1
total = 0
for w in weights:
if total + w > capacity:
days += 1
total = 0
total += w
return days <= D
left, right = max(weights), sum(weights)
while left < right:
mid = (left + right) // 2
if canShip(mid):
right = mid
else:
left = mid + 1
return left
class Solution {
public:
bool canShip(vector<int>& weights, int D, int capacity) {
int days = 1, total = 0;
for (int w : weights) {
if (total + w > capacity) {
days++;
total = 0;
}
total += w;
}
return days <= D;
}
int shipWithinDays(vector<int>& weights, int D) {
int left = *max_element(weights.begin(), weights.end());
int right = accumulate(weights.begin(), weights.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, D, mid))
right = mid;
else
left = mid + 1;
}
return left;
}
};
class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = 0, right = 0;
for (int w : weights) {
left = Math.max(left, w);
right += w;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canShip(int[] weights, int D, int capacity) {
int days = 1, total = 0;
for (int w : weights) {
if (total + w > capacity) {
days++;
total = 0;
}
total += w;
}
return days <= D;
}
}
var shipWithinDays = function(weights, D) {
function canShip(capacity) {
let days = 1, total = 0;
for (let w of weights) {
if (total + w > capacity) {
days++;
total = 0;
}
total += w;
}
return days <= D;
}
let left = Math.max(...weights), right = weights.reduce((a, b) => a + b, 0);
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (canShip(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
You are given an array weights where weights[i] is the weight of the i-th package, and an integer D representing the number of days within which all the packages must be shipped.
Each day, you must load the packages onto a ship in the order given by the array. The ship has a maximum capacity (the same every day), and you cannot load more weight than this capacity in a single day.
Packages must be shipped in order; you cannot skip or reorder them. Your goal is to find the minimum ship capacity required to ship all packages within D days.
D days.
At first, you might consider trying every possible way to split the packages into D groups, but this quickly becomes infeasible as the number of packages grows.
Instead, notice that the key challenge is to determine the smallest possible ship capacity that allows us to ship all packages in order within D days.
If the ship's capacity is very large (e.g., the sum of all weights), we can ship all packages in one day. If the capacity is very small (e.g., the heaviest package), it might require many days.
The problem is thus about finding the minimum ship capacity for which it is possible to ship all packages within D days.
This is a classic "search for minimum feasible value" problem, which is well-suited to a binary search approach.
D days using that capacity.D, the capacity is feasible.This approach is efficient because it avoids checking every possible grouping, and instead leverages the monotonic nature of the problem (i.e., increasing the capacity never makes the task harder).
Suppose weights = [1,2,3,4,5,6,7,8,9,10] and D = 5.
This step-by-step halving of the search interval quickly homes in on the answer.
O(log(S)) time, where S is the sum of all weights minus the max weight.
weights array once to simulate the shipping, which takes O(N) time.
O(N log S).
O(1), since we only use a few variables for counting and boundaries.
The problem is about finding the minimum ship capacity to deliver packages within a given number of days, shipping packages in order and without exceeding the daily capacity. By recognizing the problem's monotonic nature, we can use binary search to efficiently find the answer, checking each candidate capacity with a simple simulation. This approach is both efficient and elegant, avoiding brute-force enumeration and leveraging a classic algorithmic technique.