Book Allocation Problem
Hard · Binary Search · Array · Binary Search · Greedy
Problem
You are given an array pages, where pages[i] is the number of pages in book i, and an integer m, the number of students. Hand out the books under these rules:
- Every book goes to exactly one student.
- Each student receives at least one book.
- Each student receives a contiguous block of books, in the given order.
Return the smallest possible value of the most pages any single student reads. If there are more students than books, no allocation exists: return -1.
Examples
Input: pages = [15,20,30,10], m = 2 Output: 40
Splitting as [15, 20] and [30, 10] gives 35 and 40 pages. The other two splits leave one student with 60 or 65 pages.
Input: pages = [5,5,5,5], m = 4 Output: 5
Each student gets one book.
Input: pages = [12,7], m = 3 Output: -1
Three students cannot each receive a book from only two books.
Constraints
- 1 <= len(pages) <= 10^5
- 1 <= pages[i] <= 10^6
- 1 <= m <= 10^5
- The answer can exceed 2^31 - 1: use 64-bit integers
Approaches
- Baseline: table over students and prefixes — time O(m · n²), space O(m · n)
Follow-up
Why may a limit that needs fewer than m students still count? Any block with two or more books can be split, adding a student without raising anyone above the limit, and there are at least m books. The use cases ask the greedy count on its own, and the reverse goal: make the lightest reader read as much as possible.
Related problems
Start free on Cariara · Coding problems · System design studio
