LeetCode Solutions
1011. Capacity To Ship Packages Within D Days
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int l = *max_element(begin(weights), end(weights));
int r = accumulate(begin(weights), end(weights), 0);
while (l < r) {
const int m = (l + r) / 2;
if (shipDays(weights, m) <= days)
r = m;
else
l = m + 1;
}
return l;
}
private:
int shipDays(const vector<int>& weights, int shipCapacity) {
int days = 1;
int capacity = 0;
for (const int weight : weights) {
if (capacity + weight > shipCapacity) {
++days;
capacity = weight;
} else {
capacity += weight;
}
}
return days;
};
};
class Solution {
public int shipWithinDays(int[] weights, int days) {
int l = Arrays.stream(weights).max().getAsInt();
int r = Arrays.stream(weights).sum();
while (l < r) {
final int m = (l + r) / 2;
if (shipDays(weights, m) <= days)
r = m;
else
l = m + 1;
}
return l;
}
private int shipDays(int[] weights, int shipCapacity) {
int days = 1;
int capacity = 0;
for (final int weight : weights) {
if (capacity + weight > shipCapacity) {
++days;
capacity = weight;
} else
capacity += weight;
}
return days;
}
}
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
l = max(weights)
r = sum(weights)
def shipDays(shipCapacity: int) -> int:
days = 1
capacity = 0
for weight in weights:
if capacity + weight > shipCapacity:
days += 1
capacity = weight
else:
capacity += weight
return days
while l < r:
m = (l + r) // 2
if shipDays(m) <= days:
r = m
else:
l = m + 1
return l