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 <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6bool canShip(const vector<int>& weights, int days, int capacity) {
7 int total = 0, dayCount = 1;
8 for (int weight : weights) {
9 if (total + weight > capacity) {
10 dayCount++;
11 total = 0;
12 }
13 total += weight;
14 }
15 return dayCount <= days;
16}
17
18int shipWithinDays(vector<int>& weights, int days) {
19 int left = *max_element(weights.begin(), weights.end());
20 int right = accumulate(weights.begin(), weights.end(), 0);
21 while (left < right) {
22 int mid = left + (right - left) / 2;
23 if (canShip(weights, days, mid)) {
24 right = mid;
25 } else {
26 left = mid + 1;
27 }
28 }
29 return left;
30}
31
32int main() {
33 vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
34 int days = 5;
35 cout << shipWithinDays(weights, days) << endl; // Output: 15
36 return 0;
37}In this C++ solution, we use the standard library functions max_element and accumulate to determine the initial bounds for the binary search. The core logic remains similar to the C implementation, adjusting search bounds based on the feasibility of a given capacity.
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).
1import java.util.*;
2
3class Solution {
4 public boolean canShip(int[] weights, int days, int capacity) {
5 int total = 0, dayCount = 1;
6 for (int weight : weights) {
7 if (total + weight > capacity) {
8 dayCount++;
9 total = 0;
10 }
11 total += weight;
12 }
13 return dayCount <= days;
14 }
15
16 public int shipWithinDays(int[] weights, int days) {
17 int left = Arrays.stream(weights).max().getAsInt();
18 while (!canShip(weights, days, left)) {
19 left++;
20 }
21 return left;
22 }
23
24 public static void main(String[] args) {
25 Solution sol = new Solution();
26 int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
27 int days = 5;
28 System.out.println(sol.shipWithinDays(weights, days)); // Output: 15
29 }
30}In this Java solution, we start with the maximum weight and incrementally attempt higher capacities to find the minimum that meets the shipping constraints. The canShip method is used to validate each capacity value incrementally.