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.
def shipWithinDays(weights, D):
left, right = max(weights), sum(weights) while left < right:
mid, ships, sum = (left + right) // 2, 1, 0 for weight in weights:
sum += weight if sum > mid:
sum = weight ships += 1 if ships > D:
left = mid + 1 else:
right = mid return leftFollow-up:
What if the weights of the packages are not integers?
