099 — Allocate Minimum Pages (Book Allocation)

098-এ maximize-এ মাথা উল্টালে। এবার আবার minimize, কিন্তু একটা নতুন স্বাদে: "minimize the maximum" — সবচেয়ে ভারী বোঝাটাকে যত হালকা সম্ভব করা। কয়েকটা বই কয়েকজন ছাত্রকে ভাগ করে দিতে হবে, যাতে যে সবচেয়ে বেশি পড়ার চাপ পায়, তার চাপটাও সবচেয়ে কম হয়। এই "max-কে minimize" pattern interview-র সবচেয়ে প্রিয় BSoA — আর 100 (Split Array) হলো এর হুবহু যমজ।

Source

• Original source: Classic interview problem (book allocation)
• Platform: — (classic; related LeetCode: Split Array Largest Sum — https://leetcode.com/problems/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

1. Problem in simple words

কতগুলো বই সারিবদ্ধ, books[i] হলো i-তম বইয়ের পৃষ্ঠা সংখ্যা। এগুলো m জন ছাত্রের মধ্যে ভাগ করতে হবে।

নিয়ম: প্রত্যেক ছাত্র পরপর (consecutive) কয়েকটা বই পায় (মাঝখান থেকে তুলে নেওয়া যায় না, ক্রম বদলানো যায় না), আর প্রতিটা বই ঠিক একজন পায়। কোনো ছাত্রের মোট পৃষ্ঠা = তার পাওয়া বইগুলোর যোগফল।

প্রশ্ন: এমনভাবে ভাগ করো যাতে যে ছাত্র সবচেয়ে বেশি পৃষ্ঠা পায়, তার পৃষ্ঠা সংখ্যা সবচেয়ে কম হয়। সেই সর্বনিম্ন-সর্বোচ্চ মানটাই উত্তর। (m জন ছাত্রের জন্য যথেষ্ট বই না থাকলে অসম্ভব — সাধারণত m <= len(books) ধরা হয়।)

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 = উত্তর।

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 কত গল্পে ফেরে।

4. Real-life analogy

ভাবো একটা লম্বা কাজের তালিকা (পরপর সাজানো), আর কয়েকজন কর্মী। কাজগুলোর ক্রম বদলানো যাবে না, আর প্রত্যেক কর্মী একটানা পরপর কয়েকটা কাজ নেবে।

তুমি চাও কাজ এমনভাবে ভাগ হোক যাতে সবচেয়ে ব্যস্ত কর্মীর বোঝাও যত কম সম্ভব হয় — যাতে কেউ অতিরিক্ত চাপে না পড়ে। তুমি একটা সীমা ঠিক করো ("কেউ X ঘণ্টার বেশি কাজ পাবে না") আর দেখো এতে কতজন কর্মী লাগে। সীমা ছোট হলে বেশি কর্মী লাগে; তুমি খুঁজছ সবচেয়ে ছোট সীমা যাতে তোমার হাতের কর্মীতেই কুলোয়।

5. Visual explanation

books = [12, 34, 67, 90], m = 2। কয়েকটা cap-এর জন্য কতজন ছাত্র আর "≤ 2?":

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 — এর চেয়ে কম সর্বোচ্চ সম্ভব না।)

6. Example input and output

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

7. Brute force thinking

cap = max(books) থেকে শুরু (এর কম হলে সবচেয়ে মোটা বই-ই কেউ নিতে পারে না) করে এক এক করে বাড়াও; প্রথম যে cap-এ ছাত্র সংখ্যা ≤ m, সেটাই উত্তর:

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)) — অচল।

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-এর হুবহু কাঠামো):

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 বা ভুল।

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-তেই উত্তর স্থির।

12. Python solution

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

if m > len(books): return -1

ছাত্র সংখ্যা বইয়ের চেয়ে বেশি হলে প্রত্যেককে অন্তত একটা বই দেওয়া অসম্ভব — তাই আগেই -1। এই edge না সামলালে নিচের যুক্তি ভুল হতো।

cnt, cur = 1, 0

cnt = এ পর্যন্ত লাগা ছাত্র (অন্তত 1), cur = চলতি ছাত্রের জমা পৃষ্ঠা।

if cur + b > cap: cnt += 1; cur = 0

চলতি ছাত্রের কাছে এই বই দিলে cap ছাড়িয়ে যায় → এই বই নতুন ছাত্রকে দাও (cnt += 1), তার জমা শূন্য থেকে শুরু। (b <= cap সবসময়, কারণ lo >= max(books) — তাই এক বই কখনো একা cap ছাড়ায় না।)

lo, hi = max(books), sum(books)

answer space। lo = max(books): সবচেয়ে মোটা বই তো একজনকে পুরোটা নিতে হবে, cap তার চেয়ে ছোট হলে অসম্ভব। hi = sum(books): এক ছাত্রে সব — সবসময় feasible।

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!।

14. Output walkthrough

চালালে যা ছাপবে:

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!।

15. Time complexity

O(n log(sum(books))) — answer space [max, sum]-এ binary search (log(sum) ধাপ), প্রতি ধাপে greedy check O(n)। বড় input-এও দ্রুত।

16. Space complexity

O(1) — check-এ শুধু cnt, cur; কোনো বাড়তি array না। lo, hi, mid ছাড়া আর কিছু লাগে না।

17. Common mistakes

1. m > len(books) চেক ভুলে যাওয়া — অসম্ভব কেস না সামলালে ভুল উত্তর/crash; শুরুতেই -1।
2. lo = 1 দিয়ে শুরু — cap যদি max(books)-এর ছোট হয়, সবচেয়ে মোটা বই কেউ নিতে পারে না; lo = max(books)।
3. cnt 0 থেকে শুরু — অন্তত 1 ছাত্র লাগবেই; cnt = 1, নইলে এক কম গোনা।
4. maximize move লিখে ফেলা — এটা minimize the maximum; পাশ করলে hi = mid (ছোট cap), lo = mid না। 098-এর সাথে গুলিও না।
5. non-consecutive ভাগ ধরে নেওয়া — ছাত্র শুধু পরপর বই পায়; greedy সামনে থেকেই কাটে, এলোমেলো ভাগ ভুল।

18. Harder problems that inherit this idea

• LeetCode — Split Array Largest Sum (https://leetcode.com/problems/split-array-largest-sum/) — আক্ষরিক যমজ; পরের problem 100-এ বিস্তারিত (DP সমাধানও আছে)।
• LeetCode — Minimum Number of Days to Make m Bouquets (https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/) — ভিন্ন গল্প, একই minimize + greedy check।
• 100 (Split Array Largest Sum) — এই repo-রই পরের ধাপ; কোড প্রায় copy-paste, শুধু "ছাত্র"-এর জায়গায় "subarray"।

19. Pattern learned

Minimize the maximum (via minimize BSoA + greedy split) — guess করো max-load cap, greedy-তে ভাগ গুনে <= m check; lo = max, hi = sum; পাশ → hi = mid। বড় শিক্ষা: "সবচেয়ে বড়টাকে যত ছোট সম্ভব" = max guess করে 'কয়টা ভাগ লাগে?' check — Koko/Ship-এর হুবহু কাঠামো। Ship আর Pages আর Split — তিনটেই এক হাড়-পাঁজরের।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Allocate Pages = minimize-the-maximum BSoA, Ship-এর যমজ; answer = max-load, check = greedy-তে ছাত্র গুনে ≤ m, lo=max(b), hi=sum(b), পাশ→hi=mid। আগে m>n → -1 সামলাই। 'minimize the max load' = এই ছক।"

পরের ধাপ → 100 — Split Array Largest Sum (আক্ষরিক যমজ — Hard, কিন্তু কোড প্রায় এক)। সম্পর্কিত → 097 — Ship Packages Within D Days।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

minimize-the-maximum — cap guess করে greedy-তে ছাত্র গুনি; lo = max(books), hi = sum(books); পাশ → hi = mid।

// 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/ভুল উত্তর।

22. TypeScript solution (with test cases)

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<readonly [number[], number, number]> = [
  [[12, 34, 67, 90], 2, 113], [[10, 20, 30, 40], 2, 60],
  [[10, 20, 30, 40], 1, 100], [[10, 20, 30, 40], 4, 40], [[15, 17, 20], 5, -1],
];
for (const [b, m, want] of cases) expect(allocatePages(b, m), want, `m=${m}`);
console.log("সব TS test pass!");

TS টীকা: can return boolean annotate করায় greedy check-এ <= m ভুলে গেলে বা cnt return করলে compile-time-এ ধরা পড়ে; minimize-the-maximum-এর move-শর্ত type-সুরক্ষিত থাকে।

23. কোথায় কাজে লাগে (real-world use)

• Load balancing / partitioning: consecutive কাজ/ফাইল কয়েকটা worker-এ ভাগ যাতে সবচেয়ে ব্যস্ত worker-এর বোঝা সবচেয়ে কম — fair scheduling।
• Sharding / chunking: বড় dataset কে k shard-এ ভাগ করে max shard size minimize (DB partition, parallel job)।
• Printing / streaming: পরপর pages/segments কয়েকটা machine বা buffer-এ বণ্টন, max লোড কমিয়ে।
• Split array largest sum: আক্ষরিক যমজ problem — array কে m subarray-তে ভেঙে largest sum minimize। মূল pattern — "'সবচেয়ে বড় ভাগকে যত ছোট সম্ভব' = max guess করে 'কয়টা ভাগ লাগে?' check (minimize BSoA + greedy)" — partition/scheduling জুড়ে বড় ছবিতে ফেরে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।