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 ith package, the weight of the package is weights[i]. You are required to deliver them in order, and in order to minimize the cost, you want to deliver the packages in one truck once per day, with a capacity as small as possible to save truck rental cost. What is the minimum 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 capacity of the truck.

Examples

Example 1:

Input:

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
d = 5

Output: 15

Explanation:

The 1st day we deliver the first 5 package. The 2nd 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.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade