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.
1using System;
2using System.Linq;
3
4class Solution {
5 public bool CanShip(int[] weights, int days, int capacity) {
6 int total = 0, dayCount = 1;
7 foreach (int weight in weights) {
8 if (total + weight > capacity) {
9 dayCount++;
10 total = 0;
11 }
12 total += weight;
13 }
14 return dayCount <= days;
15 }
16
17 public int ShipWithinDays(int[] weights, int days) {
18 int left = weights.Max();
19 int right = weights.Sum();
20 while (left < right) {
21 int mid = left + (right - left) / 2;
22 if (CanShip(weights, days, mid)) {
23 right = mid;
24 } else {
25 left = mid + 1;
26 }
27 }
28 return left;
29 }
30
31 static void Main() {
32 Solution solution = new Solution();
33 int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
34 int days = 5;
35 Console.WriteLine(solution.ShipWithinDays(weights, days)); // Output: 15
36 }
37}In C#, we utilize LINQ methods to determine the initial values for the binary search. The core logic is encapsulated within the CanShip function, which verifies the feasibility of a given ship capacity. The primary method, ShipWithinDays, executes the binary search strategy based on this can-ship check.
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).
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 = max(weights)
13 while not self.canShip(weights, days, left):
14 left += 1
15 return left
16
17# Example usage
18solution = Solution()
19weights = [1,2,3,4,5,6,7,8,9,10]
20days = 5
21print(solution.shipWithinDays(weights, days)) # Output: 15The Python solution uses a loop to incrementally increase the shipping capacity from the maximum weight until a feasible capacity is found that meets the constraint. The method canShip evaluates each capacity.