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.
1#include <stdio.h>
2
3int canShip(int weights[], int size, int days, int capacity) {
4 int total = 0, dayCount = 1;
5 for (int i = 0; i < size; i++) {
6 if (total + weights[i] > capacity) {
7 dayCount++;
8 total = 0;
9 }
10 total += weights[i];
11 }
12 return dayCount <= days;
13}
14
15int shipWithinDays(int* weights, int size, int days) {
16 int left = weights[0], right = 0;
17 for (int i = 0; i < size; i++) {
18 if (weights[i] > left) { left = weights[i]; }
19 right += weights[i];
20 }
21 while (left < right) {
22 int mid = left + (right - left) / 2;
23 if (canShip(weights, size, days, mid)) {
24 right = mid;
25 } else {
26 left = mid + 1;
27 }
28 }
29 return left;
30}
31
32int main() {
33 int weights[] = {1,2,3,4,5,6,7,8,9,10};
34 int days = 5;
35 int size = sizeof(weights)/sizeof(weights[0]);
36 printf("%d\n", shipWithinDays(weights, size, days)); // Output: 15
37 return 0;
38}In this C solution, we define a helper function canShip which checks if a given capacity can ship all packages within the specified days. We use binary search in the shipWithinDays function to find the minimal capacity required, by adjusting the search bounds based on the feasibility determined by canShip.
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).
1#include <stdio.h>
2
3int canShip(int weights[], int size, int days, int capacity) {
4 int total = 0, dayCount = 1;
5 for (int i = 0; i < size; i++) {
6 if (total + weights[i] > capacity) {
7 dayCount++;
8 total = 0;
9 }
10 total += weights[i];
11 }
12 return dayCount <= days;
13}
14
15int shipWithinDays(int* weights, int size, int days) {
16 int left = weights[0];
17 for (int i = 0; i < size; i++) {
18 if (weights[i] > left) { left = weights[i]; }
19 }
20 while (!canShip(weights, size, days, left)) {
21 left++;
22 }
23 return left;
24}
25
26int main() {
27 int weights[] = {1,2,3,4,5,6,7,8,9,10};
28 int days = 5;
29 int size = sizeof(weights)/sizeof(weights[0]);
30 printf("%d\n", shipWithinDays(weights, size, days)); // Output: 15
31 return 0;
32}This C solution incrementally increases the capacity from the maximum package weight. With each increment, we check if the current capacity is sufficient to ship within the given days using canShip. This approach may take longer due to its linear simulation nature.