Capacity To Ship Packages
Given the weights and capacities of a list of packages and a list of ships, determine the maximum number of packages that can be shipped.
Constraints:
- 1 <= packages.length <= 10^5
- 1 <= ships.length <= 10^5
- 1 <= packages[i] <= 10^5
- 1 <= ships[i] <= 10^5
Examples:
Input: [2,3,4,5], [1,2,3,4,5,6,7,8,9,10]
Output: 4
Explanation: We can ship packages of weights 2, 3, 4, and 5 using ships of capacities 2, 3, 4, and 5 respectively.
Solutions
Greedy Algorithm
The solution uses a binary search approach to find the minimum capacity required to ship all packages within D days. It starts by initializing the left and right pointers to the maximum weight of a package and the total weight of all packages respectively. Then, it iteratively calculates the mid capacity and checks if it is possible to ship all packages within D days using this capacity. If it is not possible, it updates the left pointer to mid + 1. Otherwise, it updates the right pointer to mid. The process continues until the left and right pointers converge, at which point the minimum capacity required to ship all packages within D days is returned.
function shipWithinDays(weights, D) {
let left = Math.max(...weights),
right = weights.reduce((a, b) => a + b, 0);
while (left < right) {
let mid = Math.floor((left + right) / 2),
ships = 1,
sum = 0;
for (let weight of weights) {
sum += weight;
if (sum > mid) {
sum = weight;
ships++;
}
}
if (ships > D) left = mid + 1;
else right = mid;
}
return left;
}
Follow-up:
What if the weights of the packages are not integers?
