Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Capacity to Ship Packages Within D Days

Medium
binary-searchgreedyanswer-space

A conveyor belt has packages with given weights that must be shipped in order, splitting them across at most days days. The ship has a fixed daily capacity. Return the minimum capacity that ships everything within days days.

Input

  • Line 1: space-separated package weights (in belt order)
  • Line 2: the integer days

Output: the minimum ship capacity.

Example 1
Input:
1 2 3 4 5 6 7 8 9 10
5
Output:
15

Days: (1 2 3 4 5), (6 7), (8), (9), (10).

Example 2
Input:
3 2 2 4 1 4
3
Output:
6
Example 3
Input:
1 2 3 1 1
4
Output:
3

Constraints

  • 1 ≤ weights.length ≤ 5·10^4
  • 1 ≤ weights[i] ≤ 500
  • 1 ≤ days ≤ weights.length
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.