Capacity To Ship Packages Within D Days

Moderate

0/80

Average time to solve is 15m

Contributed by

127 upvotes

Asked in companies

Problem statement

You are the owner of a Shipment company. You use conveyor belts to ship packages from one port to another. The packages must be shipped within 'd' days.

The weights of the packages are given in an array 'weights'. The packages are loaded on the conveyor belts every day in the same order as they appear in the array. The loaded weights must not exceed the maximum weight capacity of the ship.

Find out the least-weight capacity so that you can ship all the packages within 'd' days.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two integers, ‘n’ and ‘d’, denoting the size of the array ‘weights’ and the maximum weight capacity of the ship.

The second line contains ‘n’ integers denoting the elements of the array ‘weights’.

Output Format:

Return the least weight capacity so that you can ship all the packages within 'd' days.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Sample Input 1:

8 5
5 4 5 2 3 4 5 6

Sample Output 1:

Explanation for Sample Input 1:

In the test case, the given weights are [5,4,5,2,3,4,5,6] and these are needed to be shipped in 5 days. We can divide these weights in the following manner:
Day         Weights            Total
1        -   5, 4          -    9
2        -   5, 2          -    7
3        -   3, 4          -    7
4        -   5             -    5
5        -   6             -    6
The least weight capacity needed is 9, which is the total amount of weight that needs to be taken on Day 1.

Sample Input 2:

10 1
1 2 3 4 5 6 7 8 9 10

Sample Output 2:

Constraints:

1 <= n <= 10^5
1 <= d <= 10^5
1 <= weights[i] <= 500

Time Limit: 1 sec

Console