Books have page counts, and they must be given to students in order, with each student getting a contiguous block. Minimize the largest number of pages any student reads.
DSA Animator › DSA Revision › Binary Search › Allocate Minimum Number of Pages
Remember: this is the same problem as split array largest sum. Binary search the limit, and count students greedily. The video solves Allocate Minimum Number of Pages (GFG, Hard) with the Binary Search on Answer pattern from the Binary Search topic, and you can replay every step in the interactive Allocate Minimum Number of Pages animation.
Books have page counts, and they must be given to students in order, with each student getting a contiguous block. Minimize the largest number of pages any student reads.
For books 12, 34, 67, 90 and 2 students, the answer is 113. One student reads 12, 34, 67, and the other reads 90.
Trying every way to split the books is exponential. But if a page limit works, every bigger limit works too.
Binary search the page limit between the largest book and the total. For a limit, give books to a student until the next one would exceed it, then move to the next student. If the students needed are at most the given number, try smaller.
The range is 90 to 203. 146 works, and so does 118. 104 and 111 need 3 students, which is too many. 115 works, 113 works, and 112 does not. So the answer is 113.
In code, low is the largest book and high is the total pages. The check counts students greedily. Move high to mid when it works, otherwise move low past mid. If there are more students than books, return minus 1, and it's O of n log of the sum.
Remember: this is the same problem as split array largest sum. Binary search the limit, and count students greedily.