dsa · hard

Balance the Pipeline Load

A batch of jobs must flow through lanes processing lanes in the given order: cut jobs into exactly lanes contiguous, non-empty blocks (every job goes to exactly one block, blocks keep their order). A lane finishes when its block is done, so the whole batch takes as long as the heaviest block, where a block's load is the sum of its job durations.

Arguments

Choose the cut that minimises the heaviest block's load and return that minimum. It is always possible because there are at least as many jobs as lanes.

Example

jobs = [7,2,5,10,8], lanes = 2

Try the split after the second job: blocks [7,2] and [5,10,8] load 9 and 23 → heaviest 23. Split after the third: [7,2,5] and [10,8] load 14 and 18 → heaviest 18. Split after the fourth: [7,2,5,10] and [8] load 24 and 8 → heaviest 24. The best heaviest block is 18.

jobs = [1,2,3,4,5], lanes = 2 → [1,2,3,4] vs [5] gives heaviest 10; [1,2,3] vs [4,5] gives 9 — the minimum is 9.

Constraints

1 <= jobs.length <= 10^5 1 <= lanes <= min(50, jobs.length) 0 <= jobs[i] <= 10^6 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[7,2,5,10,8]
2

Expected:
18

Example 2

Input:
[1,2,3,4,5]
2

Expected:
9

Example 3

Input:
[1,4,4]
3

Expected:
4

Open in the Dojo editor