Problem link ও উৎস
- **Original source:** Classic interview problem (book allocation)
- **Platform:** — (classic; related LeetCode: Split Array Largest Sum —
)
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Medium
- **Pattern:** minimize max load (সবচেয়ে বড় ভাগকে minimize)
- **Basic idea inherited from:** 097 — Ship Packages Within D Days
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো বই সারিবদ্ধ, `books[i]` হলো i-তম বইয়ের পৃষ্ঠা সংখ্যা। এগুলো `m` জন ছাত্রের মধ্যে ভাগ করতে হবে।
নিয়ম: প্রত্যেক ছাত্র **পরপর (consecutive) কয়েকটা** বই পায় (মাঝখান থেকে তুলে নেওয়া যায় না, ক্রম বদলানো যায় না), আর প্রতিটা বই ঠিক একজন পায়। কোনো ছাত্রের মোট পৃষ্ঠা = তার পাওয়া বইগুলোর যোগফল।
প্রশ্ন: এমনভাবে ভাগ করো যাতে **যে ছাত্র সবচেয়ে বেশি পৃষ্ঠা পায়, তার পৃষ্ঠা সংখ্যা সবচেয়ে কম** হয়। সেই সর্বনিম্ন-সর্বোচ্চ মানটাই উত্তর। (m জন ছাত্রের জন্য যথেষ্ট বই না থাকলে অসম্ভব — সাধারণত `m <= len(books)` ধরা হয়।)
### Input ও output {#6-example-input-and-output}
```text
books m -> min max-pages (ব্যাখ্যা)
-----------------------------------------------------
[12, 34, 67, 90] 2 -> 113 ([12,34,67]=113 | [90])
[10, 20, 30, 40] 2 -> 60 ([10,20,30]=60 | [40])
[10, 20, 30, 40] 1 -> 100 (1 ছাত্র → sum)
[10, 20, 30, 40] 4 -> 40 (4 ছাত্র → প্রতি বই আলাদা → max)
[15, 17, 20] 5 -> -1 (m > বই সংখ্যা → অসম্ভব)
```
দুই সীমান্ত: **m = 1** → এক ছাত্র সব পড়ে → `sum(books)`। **m = বই সংখ্যা** → প্রতি বই আলাদা ছাত্র → `max(books)`। আর **m > বই সংখ্যা** হলে প্রত্যেককে অন্তত একটা বই দেওয়া যায় না → অসম্ভব (`-1`)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা লম্বা কাজের তালিকা (পরপর সাজানো), আর কয়েকজন কর্মী। কাজগুলোর ক্রম বদলানো যাবে না, আর প্রত্যেক কর্মী একটানা পরপর কয়েকটা কাজ নেবে।
তুমি চাও কাজ এমনভাবে ভাগ হোক যাতে **সবচেয়ে ব্যস্ত কর্মীর বোঝাও যত কম সম্ভব** হয় — যাতে কেউ অতিরিক্ত চাপে না পড়ে। তুমি একটা সীমা ঠিক করো ("কেউ X ঘণ্টার বেশি কাজ পাবে না") আর দেখো এতে কতজন কর্মী লাগে। সীমা ছোট হলে বেশি কর্মী লাগে; তুমি খুঁজছ সবচেয়ে ছোট সীমা যাতে তোমার হাতের কর্মীতেই কুলোয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
097 (Ship Packages) থেকে — আসলে এটা **প্রায় হুবহু একই problem**, শুধু শব্দ বদলেছে:
- Ship: weights → days দিনে ভাগ, capacity guess, check "দিন ≤ days?"
- Pages: books → m ছাত্রে ভাগ, max-pages guess, check "ছাত্র ≤ m?"
"days" আর "students" দুটোই আসলে "কতগুলো consecutive ভাগ"। check-এর greedy পাসও হুবহু এক (যোগ করো, cap ছাড়ালে নতুন ভাগ)। এই মিলটা দেখতে পারাই আসল শিক্ষা — একটা template কত গল্পে ফেরে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
**minimize ঘরানার BSoA**, কিন্তু লক্ষ্য "max-কে minimize"। উত্তর (সর্বনিম্ন সম্ভব সর্বোচ্চ-বোঝা) সরাসরি বের না করে, একটা সীমা `cap` guess করি আর check: "কোনো ছাত্রের যোগফল `cap` না ছাড়িয়ে ভাগ করলে, কয়জন ছাত্র লাগে — সেটা কি ≤ m?"
observation — **cap বাড়ালে কম ছাত্র লাগে (বা সমান)।** তাই check-এর সিঁড়ি **F F F T T T**: ছোট cap-এ অনেক ছাত্র দরকার (>m, পারে না), একটা জায়গার পর m-এর মধ্যে নেমে আসে। প্রথম T = সবচেয়ে ছোট feasible cap = উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
cap = `max(books)` থেকে শুরু (এর কম হলে সবচেয়ে মোটা বই-ই কেউ নিতে পারে না) করে এক এক করে বাড়াও; প্রথম যে cap-এ ছাত্র সংখ্যা ≤ m, সেটাই উত্তর:
```python
def alloc_brute(books, m):
if m > len(books):
return -1
def students(cap):
cnt, cur = 1, 0
for b in books:
if cur + b > cap: # এই ছাত্রের কাছে আর ধরছে না
cnt += 1
cur = 0
cur += b
return cnt
cap = max(books)
while students(cap) > m:
cap += 1
return cap
```
`students(cap)` greedy-তে গোনে: যোগ করতে থাকো, cap ছাড়ালে নতুন ছাত্র। তারপর `max(books)` থেকে cap বাড়িয়ে প্রথম feasible-এ থামি। 097-এর `need(cap)`-এর সাথে হুবহু এক যুক্তি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
cap-এর পরিসর `max(books)` থেকে `sum(books)` — বিশাল (10^9 স্কেল)। প্রতি cap-এ greedy O(n)। তাই **O(n · sum(books))** — অচল।
```text
sum(books) ≈ 10^9, n = 10^5 হলে:
brute force : ~10^14 operation (অসম্ভব ধীর, TLE)
binary search : ~30 × 10^5 ≈ 3×10^6 (O(n log sum), দ্রুত)
```
মূল শিক্ষা: `students(cap)` monotonic decreasing — তাই cap এক এক করে না বাড়িয়ে binary search-এ অর্ধেক বাদ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: `students(cap)` monotonic, তাই `students(cap) <= m`-এর সিঁড়ি **F F F T T T**। প্রথম T খুঁজি, minimize template-এ (097-এর হুবহু কাঠামো):
```python
def allocate_pages(books, m):
if m > len(books):
return -1 # প্রত্যেককে অন্তত একটা বই দেওয়া যায় না
def can(cap): # cap সীমায় ছাত্র ≤ m?
cnt, cur = 1, 0
for b in books:
if cur + b > cap:
cnt += 1
cur = 0
cur += b
return cnt <= m
lo, hi = max(books), sum(books) # lo: মোটা বই তো একজনকে নিতেই হবে; hi: একজনে সব
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট cap চেষ্টা
else:
lo = mid + 1 # পারা যায় না → বড় cap লাগবে
return lo
```
প্রতি ধাপে অর্ধেক, প্রতি check O(n) → O(n log(sum(books)))।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল মোচড়: **"max-কে minimize" শোনাটা ভয়ংকর লাগে, কিন্তু একে উল্টে একটা feasibility প্রশ্নে নামাও — 'সর্বোচ্চ বোঝা cap রাখলে ক'জন লাগে?' — তারপর সেটা minimize BSoA।**
দুই খুঁটি মনে রাখো: (1) move হলো minimize-এর (পাশ → `hi = mid`), কারণ আমরা ছোট cap খুঁজছি; সিঁড়ি FFFTTT, mid নিচে ঝোঁকা — 098-এর maximize নয়। (2) answer space: `lo = max(books)` (একটা বই-ই এক ছাত্রের ন্যূনতম বোঝা, তার চেয়ে ছোট cap অসম্ভব), `hi = sum(books)` (এক ছাত্রে সব — সবসময় feasible)। আর শুরুতেই `m > n` impossible চেক — এই edge-টা ভুললেই crash বা ভুল।
### ছবিতে বোঝা {#5-visual-explanation}
`books = [12, 34, 67, 90], m = 2`। কয়েকটা cap-এর জন্য কতজন ছাত্র আর "≤ 2?":
```text
cap : 90 100 113 ... 150 ... 191
students : 4 3 3 ... 2 ... 1
≤ 2? : F F F ... T ... T
↑
প্রথম T (cap=113) → উত্তর = 113
cap=113: [12,34,67]=113 | [90]=90 → 2 জন ✓ T
cap=112: [12,34]=46 | [67]=67 (90 নিলে 157>112) | [90] → 3 জন ✗ F
```
সিঁড়ি **F F F T T T** — cap বাড়লে ছাত্র কমে, প্রথম T = সবচেয়ে ছোট feasible max-load। (উত্তর 113: ছাত্র দুজনের বোঝা 113 আর 90; সর্বোচ্চ 113 — এর চেয়ে কম সর্বোচ্চ সম্ভব না।)
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`books = [12, 34, 67, 90], m = 2` (`lo=max=90, hi=sum=203`):
| step | lo | hi | mid | students(mid) | ≤ 2? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 90 | 203 | 146 | 2 | হ্যাঁ | hi = mid = 146 |
| 2 | 90 | 146 | 118 | 2 | হ্যাঁ | hi = mid = 118 |
| 3 | 90 | 118 | 104 | 3 | না | lo = mid + 1 = 105 |
| 4 | 105 | 118 | 111 | 3 | না | lo = mid + 1 = 112 |
| 5 | 112 | 118 | 115 | 2 | হ্যাঁ | hi = mid = 115 |
| 6 | 112 | 115 | 113 | 2 | হ্যাঁ | hi = mid = 113 |
| 7 | 112 | 113 | 112 | 3 | না | lo = mid + 1 = 113 |
| — | 113 | 113 | — | — | — | lo == hi = 113 → return 113 |
উত্তর 113 ✓। লক্ষ করো cap=112-এ 3 জন লাগে (F), কিন্তু 113-এ 2 জন (T) — ঠিক সেই boundary-তেই উত্তর স্থির।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def allocate_pages(books, m):
"""m ছাত্রে consecutive ভাগ; সবচেয়ে বড় ভাগ যত ছোট সম্ভব।"""
if m > len(books):
return -1 # প্রত্যেককে অন্তত একটা বই দেওয়া অসম্ভব
def can(cap): # cap সীমায় ছাত্র সংখ্যা ≤ m?
cnt, cur = 1, 0 # অন্তত 1 ছাত্র
for b in books:
if cur + b > cap: # আর ধরছে না → নতুন ছাত্র
cnt += 1
cur = 0
cur += b
return cnt <= m
lo, hi = max(books), sum(books) # lo নিশ্চিত নিচ, hi নিশ্চিত feasible
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট cap
else:
lo = mid + 1 # পারা যায় না → বড় cap লাগবে
return lo
def alloc_brute(books, m): # ছোট input-এ cross-check
if m > len(books):
return -1
def students(cap):
cnt, cur = 1, 0
for b in books:
if cur + b > cap:
cnt += 1; cur = 0
cur += b
return cnt
cap = max(books)
while students(cap) > m:
cap += 1
return cap
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert allocate_pages([12, 34, 67, 90], 2) == 113
assert allocate_pages([10, 20, 30, 40], 2) == 60
assert allocate_pages([10, 20, 30, 40], 1) == 100 # 1 ছাত্র → sum
assert allocate_pages([10, 20, 30, 40], 4) == 40 # n ছাত্র → max
assert allocate_pages([15, 17, 20], 5) == -1 # m > বই → অসম্ভব
assert allocate_pages([100], 1) == 100 # এক বই
# brute force-এর সাথে random cross-check
import random
random.seed(17)
for _ in range(300):
n = random.randint(1, 8)
books = [random.randint(1, 30) for _ in range(n)]
m = random.randint(1, n) # 1 ≤ m ≤ n যাতে feasible
assert allocate_pages(books, m) == alloc_brute(books, m)
# boundary: উত্তর cap-এ m ছাত্র যথেষ্ট, cap-1-এ লাগে m-এর বেশি
books, m = [12, 34, 67, 90], 2
cap = allocate_pages(books, m)
def students(arr, c):
cnt, cur = 1, 0
for b in arr:
if cur + b > c:
cnt += 1; cur = 0
cur += b
return cnt
assert students(books, cap) <= m
assert students(books, cap - 1) > m
print(allocate_pages([12, 34, 67, 90], 2)) # 113
print(allocate_pages([10, 20, 30, 40], 1)) # 100
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if m > len(books): return -1
```
ছাত্র সংখ্যা বইয়ের চেয়ে বেশি হলে প্রত্যেককে অন্তত একটা বই দেওয়া অসম্ভব — তাই আগেই `-1`। এই edge না সামলালে নিচের যুক্তি ভুল হতো।
```text
cnt, cur = 1, 0
```
`cnt` = এ পর্যন্ত লাগা ছাত্র (অন্তত 1), `cur` = চলতি ছাত্রের জমা পৃষ্ঠা।
```text
if cur + b > cap: cnt += 1; cur = 0
```
চলতি ছাত্রের কাছে এই বই দিলে cap ছাড়িয়ে যায় → এই বই **নতুন ছাত্রকে** দাও (`cnt += 1`), তার জমা শূন্য থেকে শুরু। (`b <= cap` সবসময়, কারণ `lo >= max(books)` — তাই এক বই কখনো একা cap ছাড়ায় না।)
```text
lo, hi = max(books), sum(books)
```
answer space। `lo = max(books)`: সবচেয়ে মোটা বই তো একজনকে পুরোটা নিতে হবে, cap তার চেয়ে ছোট হলে অসম্ভব। `hi = sum(books)`: এক ছাত্রে সব — সবসময় feasible।
```text
if can(mid): hi = mid / else: lo = mid + 1
```
minimize move: পারলে আরও ছোট cap (`hi = mid`), না পারলে বড় cap লাগবে (`lo = mid + 1`)। 097-এর হুবহু এক।
cross-check-এ random brute force আর boundary (cap-এ m যথেষ্ট, cap-1-এ না)। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
113
100
সব test pass!
```
প্রথম: `allocate_pages([12,34,67,90], 2)` = 113 (dry run-এর ফল)। দ্বিতীয়: `[10,20,30,40]` m=1-এ = 100 (এক ছাত্র → sum)। আগের সব `assert` — random cross-check (300 কেস), impossible কেস, আর boundary — চুপচাপ pass। সবশেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
minimize-the-maximum — cap guess করে greedy-তে ছাত্র গুনি; `lo = max(books)`, `hi = sum(books)`; পাশ → `hi = mid`।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function allocatePages(books, m) {
if (m > books.length) return -1; // প্রত্যেককে অন্তত একটা বই দেওয়া অসম্ভব
const can = (cap) => { // cap সীমায় ছাত্র ≤ m?
let cnt = 1, cur = 0; // অন্তত 1 ছাত্র
for (const b of books) {
if (cur + b > cap) { cnt++; cur = 0; } // আর ধরছে না → নতুন ছাত্র
cur += b;
}
return cnt <= m;
};
let lo = Math.max(...books), hi = books.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (can(mid)) hi = mid; // পারা যায় → আরও ছোট cap
else lo = mid + 1; // পারা যায় না → বড় cap
}
return lo;
}
// brute — cross-check
function allocBrute(books, m) {
if (m > books.length) return -1;
const students = (cap) => {
let cnt = 1, cur = 0;
for (const b of books) { if (cur + b > cap) { cnt++; cur = 0; } cur += b; }
return cnt;
};
let cap = Math.max(...books);
while (students(cap) > m) cap++;
return cap;
}
// ---- test cases (file-এর example + edge case) ----
assert(allocatePages([12, 34, 67, 90], 2) === 113, "[12,34,67]|[90]");
assert(allocatePages([10, 20, 30, 40], 2) === 60, "[10,20,30]|[40]");
assert(allocatePages([10, 20, 30, 40], 1) === 100, "1 ছাত্র → sum");
assert(allocatePages([10, 20, 30, 40], 4) === 40, "n ছাত্র → max");
assert(allocatePages([15, 17, 20], 5) === -1, "m > বই → অসম্ভব");
assert(allocatePages([100], 1) === 100, "এক বই");
// brute-এর সাথে random ছোট input জুড়ে মিল (1 ≤ m ≤ n)
for (let t = 0; t < 300; t++) {
const n = 1 + Math.floor(Math.random() * 8);
const books = [];
for (let i = 0; i < n; i++) books.push(1 + Math.floor(Math.random() * 30));
const m = 1 + Math.floor(Math.random() * n);
assert(allocatePages(books, m) === allocBrute(books, m), "cross-check");
}
console.log("সব JS test pass!");
```
> **JS টীকা:** `cnt` অবশ্যই 1 থেকে শুরু (অন্তত এক ছাত্র), নাহলে এক কম গোনা। `Math.max(...books)`/`reduce` দিয়ে lo, hi — খুব বড় array-তে spread call-stack ছাড়াতে পারে, তখন loop দিয়ে max বের করো। `m > n → -1` চেক ভুললে crash/ভুল উত্তর।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function allocatePages(books: number[], m: number): number {
if (m > books.length) return -1;
const can = (cap: number): boolean => {
let cnt = 1, cur = 0;
for (const b of books) {
if (cur + b > cap) { cnt++; cur = 0; }
cur += b;
}
return cnt <= m;
};
let lo = Math.max(...books), hi = books.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (can(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray