Capacity to Ship Packages Within D Days
There are n
packages that needs to be transported from one city to another, and you need
to transport them there within d
days. For the i
th package, the weight of the package
is weights[i]
. You are required to deliver them in order with a rental truck. The rental trucks come in different sizes. The bigger trucks have greater weight capacity but cost more to rent.
To minimize cost, you want to deliver the packages in one truck once per day, with a weight capacity as small as possible to save on rental cost.
What is the minimum weight capacity of the truck that is required to deliver all packages within
d
days?
Input
weights
: A list of packages and their weights.d
: The number of days to deliver all packages.
Output
The minimum weight capacity of the truck.
Examples
Example 1:
Input:
1weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 2d = 5
Output: 15
Explanation:
The first day we deliver the first 5
package. The second day we deliver the next 2
, and
for each following days, we deliver 1
. The maximum weight delivered on each day is 15
,
so we can have a truck with a capacity of 15
. This value is the minimum.
Constraints
1 <= len(weights) <= 5 * 10^4
1 <= d <= len(weights)
1 <= weights[i] <= 500
Try it yourself
Solution
Title
Script
Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem
Ipsum
has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.
Contrary to popular belief, Lorem
Ipsum
is not simply random text.
1 >>> a = [1, 2, 3] 2 >>> a[-1] 3 3