Sharing the books so nobody reads too much

Books are lined up in a fixed order, each with a page count. They must be handed out to students so that each student gets a contiguous run of books and every book goes to somebody.

Report the smallest possible value of "the most pages any one student has to read". If there are fewer books than students, report -1.

Worked example#

Books [12, 34, 67, 90], students = 2.

So the answer is 113.

The idea#

This is the same question as the shipping one, wearing a different hat. Students are days, books are packages, pages are weights, and "the most anyone reads" is the capacity.

That is worth stopping on. Allocate minimum pages, painter partition, split array largest sum and capacity to ship in D days are the identical problem with the nouns changed. Solve one and you have solved all four.

The two halves#

Checking a guess is one pass. Given a limit, hand out books greedily: keep adding to the current student until the next book would push them over, then start a new student. Count the students used. Greedy is right here, and it is worth knowing why: giving a student fewer books than they can take cannot help, because the books are in a fixed order and the leftovers only move rightwards.

The guesses are monotone. If a limit of 113 can be met by 2 students, so can 114. If 112 cannot, neither can 111. So the possible limits are a run of no followed by a run of yes, and binary search finds the boundary.

The ends#

Low is the largest single book: no limit below it can work, because that book has to go to somebody. High is the total: one student reads everything.

The edge case#

Fewer books than students means somebody gets nothing, which the rules do not allow, so the answer is -1. Check that before searching rather than expecting the search to discover it.

Constraints#

• 1 <= books <= 100000
• 1 <= students <= 100000
• 1 <= pages[i] <= 10000