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)).

Add a follow-up question they asked
No follow-ups yet. Be the first to add one.
asked …
LeaderboardSalary
Language
Account