Packages on the conveyor belt must be transported from one port to another within D days.

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

Returns the minimum carrying capacity of a ship capable of delivering all parcels on the conveyor belt within D days.

 

Example 1:

Weights = [1,2,3,4,5,6,7,8,9,10], D = 5 output: 15

  • Day 1:1, 2, 3, 4, 5
  • Day 2:6, 7
  • Day 3:8
  • Day 4:9
  • Day 5:10

Please note that the goods must be shipped in the given order, so it is not permissible to use a vessel of 14 load capacity and divide the packing into (2, 3, 4, 5), (1, 6, 7), (8), (9), (10).

Example 2:

Weights = [3,2,2,4,1,4], D = 3 Output: 6

  • Day 1:3, 2
  • Day 2:2, 4
  • Day 3:1, 4

Example 3:

Weights = [1,2,3,1,1], D = 4

  • Day 1:1
  • Day 2:2
  • Day 3:3
  • Day 4:1, 1

 

Tip:

1 <= D <= weights.length <= 50000

1 <= weights[i] <= 500

Their thinking

Binary search ship capacity, starting search interval is [maximum package weight, total of all packages]

Because the minimum shipment must be able to carry one package, and the maximum shipment is all at once

The boundary is narrowed by calculating the number of shipping days required under the current traffic volume

code

func shipWithinDays(weights []int, D int) int {

	sum , max:=0.- 1
	for _, weight := range weights {
		sum+=weight
		if weight>max{
			max=weight
		}
	}
	l,r:=max,sum
	for l<=r {
		mid :=(r-l)/2+l
		days := countDays(mid, weights)
		if days<=D{
			r=mid- 1
		}else{
            l=mid+1}}return l
}
func countDays(ship int,weights []int) int{

	cur,days:=ship,1
	for _, weight := range weights {
		if cur>=weight{
			cur-=weight
		}else {
			cur=ship-weight
			days++
		}
	}
	return days
}
Copy the code