Problem

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Examples

Example 1:

Input:
weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output:
 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input:
weights = [3,2,2,4,1,4], days = 3
Output:
 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input:
weights = [1,2,3,1,1], days = 4
Output:
 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Solution

Method 1 - Binary Search

  • Binary search can be applied not only on sorted array but also on monotonic(https://en.wikipedia.org/wiki/Monotonic_function) search space in which our answer lies.
  • If you are able to find the start and end of your search space which is monotonic in nature , you can start thinking of applying binary search on answers(search space) in a problem.

Algorithm

Lets take eg. 3 - [3,2,2,4,1,4], D = 3. Now lets look at the algorithm steps.

  1. Determine maximum weight - Think of a maximum weight ship can carry. This is the case if it has to carry all packages in a single day. It comes out to be total of all elements=16.
  2. Determine minimum weight - Think of a minimum weight ship can carry - This is the case if it has to carry single package everyday. So minimum weight comes out to be maximum of all elements=4.
  3. Start binary search for days - Now, we start the binary search. In weights = [3,2,2,4,1,4] our search space is from low = 4 to high = 16 1.
    1. Iteration 1 - low = 4, high = 16, mid = 10, it takes us daysNeeded = 2 days. But days needed mid is more than D days, hence we reduce our capacity. So, high = mid - 1 = 9
    2. Iteration 2 - low = 4, high = 9 ⇨ mid = 6. Now, in this case it does take 3 days, which is what we wanted. So, why not reduce the capacity further. high = mid - 1 = 5.
    3. Iteration 3 - low = 4, high = 5 ⇨ mid = 4, now it takes us daysNeeded = 4 , which is more than D = 3 days. Hence, we have to increase capacity, so low = mid + 1 = 5
    4. Iteration 4 - low = 5, high = 5 ⇨ mid = 5. Still it takes daysNeeded = 4 which is more than D = 3 days. Hence, we have to increase capacity, so low = mid + 1 = 6
    5. Now, low > high, so we stop. We return capacity = 6, which we got in iteration 2.

Code

Java
class Solution {

	public int shipWithinDays(int[] weights, int days) {
		int low = 0;
		int high = 0;

		for (int w: weights) {
			low = Math.max(low, w);
			high += w;
		}

		while (low <= high) {
			int mid = low + (high - low) / 2;;

			if (canShipWithinDays(weights, days, mid)) {
				high = mid - 1; // Try for smaller capacity
			} else {
				low = mid + 1; // Increase the capacity
			}
		}

		return low; // or high, since they will converge
	}

	private boolean canShipWithinDays(int[] weights, int days, int capacity) {
		int daysNeeded = 1; // Start with one day
		int currentLoad = 0;

		for (int weight: weights) {
			if (currentLoad + weight > capacity) {
				// Start a new day
				daysNeeded++;
				currentLoad = 0;
			}

			currentLoad += weight;

			if (daysNeeded > days) {
				return false; // More days needed than allowed
			}
		}

		return true; // Possible to ship within the given days
	}
}
Python
def shipWithinDays(self, weights, D):
	left, right = max(weights), sum(weights)
	while left < right:
		mid, need, cur = (left + right) / 2, 1, 0
		for w in weights:
			if cur + w > mid:
				need += 1
				cur = 0
			cur += w
		if need > D: left = mid + 1
		else: right = mid
	return left
C++
int shipWithinDays(vector<int>& weights, int D) {
	int left = 0, right = 25000000;
	for (int w: weights)
		left = max(left, w);
	while (left < right) {
		int mid = (left + right) / 2, need = 1, cur = 0;
		for (int i = 0; i < weights.size() && need <= D; cur += weights[i++])
			if (cur + weights[i] > mid)
				cur = 0, need++;
		if (need > D) left = mid + 1;
		else right = mid;
	}
	return left;
}

Complexity

  • Time: O(n log N) where n is number of elements in array, and N is sum of all weights. The reason is
    • Finding low and high takes O(n) time
    • Finding min capacity takes O(log (max - min)) time as we are running binary search on this range, and then it takes O(n) to check if we can ship with the current capacity. Hence O ( log(max - min) * n). Lets assume min = 0, O(n log max), and max is equal to sum of all elements.
  • Space: O(1)