1011. Capacity To Ship Packages Within D Days #

Problem #

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

The i-th 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 D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 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], D = 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], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Problem Summary #

The packages on the conveyor belt must be shipped from one port to another within D days.

The weight of the i-th package on the conveyor belt is weights[i]. Each day, we load packages onto the ship in the order of the given weights. The weight we load will not exceed the maximum carrying capacity of the ship.

Return the lowest carrying capacity of the ship that can deliver all the packages on the conveyor belt within D days.

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Solution Approach #

Given an array and the number of days D, the requirement is to ship all the goods in the array exactly within D days. Find the minimum weight that the conveyor belt needs to withstand.
This problem is exactly the same as Problem 410, just with a different description. The code is completely unchanged. See Problem 410 for the explanation of the approach.

Code #


func shipWithinDays(weights []int, D int) int {
	maxNum, sum := 0, 0
	for _, num := range weights {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	if D == 1 {
		return sum
	}
	low, high := maxNum, sum
	for low < high {
		mid := low + (high-low)>>1
		if calSum(mid, D, weights) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func calSum(mid, m int, nums []int) bool {
	sum, count := 0, 0
	for _, v := range nums {
		sum += v
		if sum > mid {
			sum = v
			count++
			// To split into m parts, only m - 1 dividers are needed
			if count > m-1 {
				return false
			}
		}
	}
	return true
}