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.
int shipWithinDays(vector<int>& weights, int D) {
int left = 0, right = 0;
for (int weight : weights) {
left = max(left, weight);
right += weight;
}
while (left < right) {
int mid = left + (right - left) / 2, ships = 1, sum = 0;
for (int weight : 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?
