Use binary search to solve this coding question.
class Solution {
public:
int shipWithinDays(vector<int> &weights, int days) {
int left = 0, right = 0;
for (int i = 0; i < weights.size(); ++i) {
// The heighest capacity should be the total weight.
right += weights[i];
// The lowest capacity should be the maximum weight.
if (left < weights[i]) {
left = weights[i];
}
}
while (left < right) {
int middle = left + (right - left) / 2;
if (isPossible(weights, days, middle)) {
right = middle;
} else {
left = middle + 1;
}
}
if (isPossible(weights, days, left)) {
return left;
}
return -1;;
}
private:
bool isPossible(vector<int> &weights, int days, int capacity) {
int time = 1, load = 0;
for (int i = 0; i < weights.size(); ++i) {
if (load + weights[i] <= capacity) {
load += weights[i];
} else {
load = weights[i];
++time;
}
}
return time <= days;
}
};
weights
.
class Solution {
public:
int shipWithinDays(vector<int> &weights, int day) {
int left = 1, right = 25000000;
while (left < right) {
int middle = left + (right - left) / 2;
if (!isPossible(weights, day, middle)) {
left = middle + 1;
} else {
right = middle;
}
}
if (!isPossible(weights, day, left)) {
++left;
}
return left;
}
private:
bool isPossible(vector<int> &weights, int day, int load) {
int time = 0, shipped = 0;
for (auto &w : weights) {
if (w > load) {
// The weight of a single package (w) is greater
// than teh capacity of the ship.
return false;
}
if (shipped + w <= load) {
shipped += w;
} else {
shipped = w;
++time;
if (time > day) {
return false;
}
}
}
++time;
return time <= day;
}
};
weights
.
My Solution Solution 1: DFS (recursion) The Key Idea for Solving This Coding Question C++ Code /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
Jun 6, 2025MyCircularQueueO(k)
Apr 20, 2025O(m)
Mar 4, 2025O(n)n is the length of nums.
Feb 19, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up