Split a Manuscript's Chapters Among Editors to Minimize the Heaviest Assignment

Implement minMaxLoad

A manuscript's chapters — chapters[i] pages each — must be split among k editors, each getting a contiguous run of chapters (never splitting a single chapter, and every editor must get at least one). Find the split that minimizes the heaviest single editor's total page count, and return that minimized maximum. No load limit below the single biggest chapter could ever work (that chapter wouldn't fit under it at all), and a limit equal to the manuscript's total page count always needs just one editor — so the answer is guaranteed to fall somewhere between those two bounds. The number of editors needed only ever decreases (or stays flat) as the load limit grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate load limit). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate load limits rather than trying every possible way to split the chapters.

Example 1:

Input: chapters = [15,28,55,72], k = 2

Output: 98

Example 2:

Input: chapters = [18,24,36,42], k = 2

Output: 78

Example 3:

Input: chapters = [5,17,100,11], k = 4

Output: 100

+ 5 hidden test cases run on Submit.

Constraints:

  • 1 ≤ number of chapters ≤ 10⁴
  • 1 ≤ chapters[i] ≤ 10⁶
  • 1 ≤ k ≤ number of chapters

chapters =

[15, 28, 55, 72]

k =

2