Split a Manuscript's Chapters Among Editors to Minimize the Heaviest Assignment
Solve this Problemchapters[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.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of chapters ≤ 10⁴ - ◆
1 ≤ chapters[i] ≤ 10⁶ - ◆
1 ≤ k ≤ number of chapters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Load Limit From the Biggest Chapter Upward
BruteChapters must be assigned in order, never splitting one, and an editor's assignment continues to grow until the next chapter would push their total over some limit — at which point a new editor starts fresh. No limit below the single biggest chapter could ever work, and a limit equal to the total page count always needs just one editor — so the true answer lies between those two bounds. Try every limit in that range, in order, counting how many editors it needs; the first limit that fits within k editors is the answer, since a bigger limit can only ever need the same number of editors or fewer. Correct, but scanning every candidate limit one at a time is wasteful once the page counts get large.
O(n · (sum − max))O(1)1class Solution {
2 public int minMaxLoad(int[] chapters, int k) {
3 int maxC = 0, sum = 0;
4 for (int c : chapters) { maxC = Math.max(maxC, c); sum += c; }
5 for (int cap = maxC; cap <= sum; cap++) {
6 if (groupsNeeded(chapters, cap) <= k) return cap;
7 }
8 return sum;
9 }
10
11 private int groupsNeeded(int[] chapters, int cap) {
12 int groups = 1, load = 0;
13 for (int c : chapters) {
14 if (load + c > cap) { groups++; load = 0; }
15 load += c;
16 }
17 return groups;
18 }
19}Optimal — Binary Search on the Load Limit
OptimalThe number of editors needed only ever goes down (or stays the same) as the load limit grows — a bigger limit can never need more editors. That monotonic relationship is exactly what binary search needs: search the candidate limits between the biggest single chapter and the total page count, and whenever a candidate limit fits within k editors, remember it and try a smaller limit; otherwise it's too tight, so search bigger.
O(n · log(sum − max))O(1)1class Solution {
2 public int minMaxLoad(int[] chapters, int k) {
3 int lo = 0, hi = 0;
4 for (int c : chapters) { lo = Math.max(lo, c); hi += c; }
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (groupsNeeded(chapters, mid) <= k) {
9 ans = mid;
10 hi = mid - 1;
11 } else {
12 lo = mid + 1;
13 }
14 }
15 return ans;
16 }
17
18 private int groupsNeeded(int[] chapters, int cap) {
19 int groups = 1, load = 0;
20 for (int c : chapters) {
21 if (load + c > cap) { groups++; load = 0; }
22 load += c;
23 }
24 return groups;
25 }
26}