Problem Statement

You are given weights array of size n, where weights[i] represents the weight of the i^th package. These n packages should be shipped from one place to another place via one ship within a given days.

If you can load the ship with some packages each day (in the order given in weights[i]), find the smallest possible maximum weight the ship can carry per day without exceeding the given number of days for shipping all packages.

Examples

Example 1:

• Input: weights = [10,20,30,40,50], days = 3
• Expected Output: 60
• Justification: A capacity of 60 means shipping [10,20,30] on day 1, [40] on day 2, and [50] on day 3.

Example 2:

• Input: weights = [5,5,5,5,5,5,5,5,5,5], days = 5
• Expected Output: 10
• Justification: A capacity of 10 allows shipping two packages of weight 5 each day, perfectly fitting within 5 days.

Example 3:

• Input: weights = [4, 8, 5, 2, 6, 3, 7, 9], days = 4
• Expected Output: 13
• Justification: A capacity of 13 allows shipping [4, 8] on day 1 (total 12, close to 13 without exceeding), [5, 2, 6] on day 2 (total 13), [3, 7] on day 3 (total 10), and [9] on day 4.

Try it yourself

Try solving this question here: