Book Allocation Problem
Mahabharata — Vyasa's Fair Distribution — Assign Books to Students Minimizing the Maximum Load
m छात्रों को पुस्तकें — अधिकतम बोझ कम से कम। क्रम बनाए रखो — प्रत्येक को एक खण्ड॥
*Books for m students — minimize the maximum load. Preserve order — each gets one contiguous section.*
The Story
Given n books with pages and m students, assign each student a contiguous segment of books (books must stay in order). Minimize the maximum pages any student gets.
For `pages=[12,34,67,90]`, m=2: assign [12,34,67] and [90]. Max=113. Or [12,34] and [67,90]. Max=157. Or [12] and [34,67,90]. Max=191. Optimal=[12,34,67] and [90]? No, wait: we need m=2 segments. Min possible: [12,34,67]+[90]=113 or [12,34]+[67,90]=157 or [12]+[34,67,90]=191. Min is 113.
**Binary search on the maximum pages limit:** - lo = max(pages) (single book must fit) - hi = sum(pages) (all to one student) - Feasibility: greedy assign pages in order, start new student when limit exceeded
```java boolean canAllocate(int[] A, int M, int limit) { int students=1, current=0; for (int a : A) { if (current + a > limit) { students++; current=0; } current += a; } return students <= M; } ```
This is IDENTICAL to bs-16 (Ship Packages). The problems are isomorphic: - Ship Packages: minimize capacity, d days → canShip function - Book Allocation: minimize max pages, m students → canAllocate function - Same code, different variable names.
All of bs-11, bs-12, bs-16, bs-17, bs-18 share the same binary search skeleton.
The Exhaustive Allocator
Try every possible max limit from max(pages) to sum(pages). O(n × sum).
public static int findPagesBruteForce(int[] A, int N, int M) {
if (N < M) return -1;
int lo=0,hi=0;
for (int a:A){lo=Math.max(lo,a);hi+=a;}
for (int limit=lo;limit<=hi;limit++) {
int s=1,cur=0;
for (int a:A){if(cur+a>limit){s++;cur=0;}cur+=a;}
if (s<=M) return limit;
}
return -1;
}Vyasa's Minimize-Max Binary Search
public static int findPages(int[] A, int N, int M) {
if (N < M) return -1; // Can't give each student a book
int lo = 0, hi = 0;
for (int a : A) { lo = Math.max(lo, a); hi += a; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int students = 1, current = 0;
for (int a : A) {
if (current + a > mid) { students++; current = 0; }
current += a;
}
if (students <= M) hi = mid;
else lo = mid + 1;
}
return lo;
}Step-by-Step Walkthrough
[15,17,20], M=2 lo=20,hi=52 mid=36: [15+17=32≤36],[20≤36] → 2≤2 → hi=36 mid=28: [15+17=32>28→new],[17+20=37>28→new] wait: student1=15+17? 15+17=32>28, so just [15], then 17+20=37>28 so [17], then [20]. Students=3>2 → lo=29 mid=32: [15+17=32≤32],[20≤32] → 2 ≤2 → hi=32 ...converges to 32 ✅
Deep Insight
**The isomorphism pattern:** Book Allocation ≡ Ship Packages ≡ Split Array Largest Sum (bs-18). All three: 1. Have an ordered array 2. Ask for minimum max-segment-sum with at most k segments 3. Use the same binary search + greedy feasibility template
Recognizing this equivalence is the key skill: once you know the Koko/Ship/Book pattern, you know 6+ problems.
**Edge case N < M:** Can't allocate — need at least as many books as students (each must get at least 1). Return -1.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × sum) | O(1) | Try each limit |
| Optimal | O(n log sum) | O(1) | Binary search + O(n) greedy check |
Pattern Recognition
✅ Minimize maximum pages with m students ✅ Same template as bs-16 (Ship Packages), bs-18 (Split Array) ✅ lo=max(A), hi=sum(A) ✅ Greedy: students needed with given limit **LeetCode Trigger Phrases:** → "allocate minimum pages" / book partition → "partition array into k parts minimizing maximum sum" → Ordered partition with minimum maximum
Bhagavad Gita 4.17
कर्मणो ह्यपि बोद्धव्यं बोद्धव्यं च विकर्मणः। अकर्मणश्च बोद्धव्यं गहना कर्मणो गतिः॥
The nature of action must be understood, and the nature of forbidden action also must be understood, and the nature of inaction must be understood — the path of action is difficult to comprehend.
Connection: Each student must receive a contiguous section — the books cannot be rearranged, just as karma cannot be arbitrarily reassigned. The algorithm finds the minimum maximum burden, distributing responsibility fairly while respecting the inherent order. Like the Gita's nuanced teaching on action, the problem rewards understanding the precise boundary where fair allocation becomes optimal — neither too much to any one student, nor an impossible partition.