Given N books with pages[], allocate books to M students such that each student gets at least one book, books are consecutive, and the maximum pages allocated to a student is minimized.
Input: pages=[12,34,67,90], M=2 → Output: 113Input: pages=[10,20,30,40], M=2 → Output: 60
Binary search on the answer (maximum pages). Check feasibility: can M students read all books with max <= mid?
- lo=max(pages), hi=sum(pages).
- For mid: greedily assign books until current student's pages exceed mid, then assign to next student.
- If students needed <= M: hi=mid. Else lo=mid+1.
class Solution {
public int books(int[] pages, int m) {
int lo = 0, hi = 0;
for (int p : pages) { lo = Math.max(lo, p); hi += p; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canAllocate(pages, m, mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
private boolean canAllocate(int[] pages, int m, int maxPages) {
int students = 1, current = 0;
for (int p : pages) {
if (current + p > maxPages) { students++; current = 0; }
current += p;
if (students > m) return false;
}
return true;
}
}
- Time Complexity: O(N log(sum))
- Space Complexity: O(1)