This approach utilizes a binary search to find the minimal ship capacity that can carry all packages within the specified number of days. The binary search operates over the range from the maximum value in the weights array to the sum of all weights, which are the logical lower and upper bounds for the ship capacity.
Time Complexity: O(n log m), where n is the number of packages and m is the range of the binary search (sum of weights - max weight).
Space Complexity: O(1), as we use constant extra space.
1class Solution:
2 def canShip(self, weights, days, capacity):
3 total, day_count = 0, 1
4 for weight in weights:
5 if total + weight > capacity:
6 day_count += 1
7 total = 0
8 total += weight
9 return day_count <= days
10
11 def shipWithinDays(self, weights, days):
12 left, right = max(weights), sum(weights)
13 while left < right:
14 mid = left + (right - left) // 2
15 if self.canShip(weights, days, mid):
16 right = mid
17 else:
18 left = mid + 1
19 return left
20
21# Example usage
22solution = Solution()
23weights = [1,2,3,4,5,6,7,8,9,10]
24days = 5
25print(solution.shipWithinDays(weights,days)) # Output: 15The Python solution defines a canShip method to determine the feasibility of shipping with a given capacity. The main shipWithinDays function applies binary search to find the minimum capacity required. The process iterates until the ideal capacity is found.
This approach involves greedy simulation to estimate the minimum capacity by incrementing from the largest single package weight until you find a capacity that can ship all the packages within the days. Note that this approach may take more time in the worst case due to the linear increment.
Time Complexity: O(n * C/m), where C/m is the number of increments in the worst case.
Space Complexity: O(1).
1function canShip(weights, days, capacity) {
2 let total = 0, dayCount = 1;
3 for (let weight of weights) {
4 if (total + weight > capacity) {
5 dayCount++;
6 total = 0;
7 }
8 total += weight;
9 }
10 return dayCount <= days;
11}
12
13function shipWithinDays(weights, days) {
14 let left = Math.max(...weights);
15 while (!canShip(weights, days, left)) {
16 left++;
17 }
18 return left;
19}
20
21const weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5;
22console.log(shipWithinDays(weights, days)); // Output: 15This JavaScript solution employs a simple incrementing loop to find the minimal feasible capacity from the maximum weight of the packages. It uses canShip to verify efficiency per iteration.