Allocate Minimum Number of Pages (Book Allocation)
viaLeetCode
Problem: Given the number of pages in n different books arranged in ascending order and m students, assign books to students such that each student gets a contiguous, non-empty set of books, every book is assigned, and the maximum number of pages assigned to any one student is minimized.
Constraints: 1 <= m <= n <= 10^5, pages fit in standard integer range.
Example: pages = [12, 34, 67, 90], m = 2 -> minimum possible maximum = 113 (e.g. split as [12,34,67] and [90]).
Approach: Binary search on the answer (the maximum pages a student can be allotted), with a linear feasibility check that greedily assigns consecutive books to students and counts how many students are needed for a given "max pages" cap. Time complexity O(n log(sum of pages)).
asked …