☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Book Allocation Problem

Hard TUF ID 74 A2Z

Java source ↗ Edit this article ↗

Problem

You are given n books in a row, where book i has pages[i] pages, and m students. Allocate the books so that:

The load of a student is the total number of pages they receive. Minimise the maximum load over all students and return that value. If an allocation is impossible (more students than books), return -1.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ pages[i] ≤ 10^6.

Example 1

pages = [12, 34, 67, 90], m = 2
answer = 113        // [12, 34, 67] and [90]: loads 113 and 90; the alternative [12, 34] and [67, 90] gives 157

Example 2

pages = [25, 46, 28, 49, 24], m = 4
answer = 71         // [25, 46] [28] [49] [24]: the heaviest load is 71

Example 3

pages = [1, 2, 3], m = 4
answer = -1         // four students, three books: someone gets nothing

The feasibility check

Fix a candidate limit maxPages. What is the fewest students needed so that no student exceeds the limit? Walk the books from left to right, giving each book to the current student while the running total stays within the limit; when the next book would push the total over, start a new student with that book. This greedy count is minimal because the blocks are contiguous and we only decide where to cut; postponing each cut as long as possible can never increase the number of blocks.

static int studentsNeeded(int[] pages, int maxPages) {
    int students = 1;
    long load = 0;
    for (int p : pages) {
        if (load + p > maxPages) { students++; load = 0; }
        load += p;
    }
    return students;
}

The function assumes maxPages ≥ max(pages); otherwise a single book could never be placed. Both approaches start the search at max to guarantee that.

Impossibility

If m > n, some student would get no book, so return -1 immediately. Conversely, when m ≤ n, an allocation always exists, and any limit at which the greedy scan needs at most m students is achievable with exactly m students: a block that holds two or more books can be split into two blocks without raising any load, and since n ≥ m there are always enough books to keep splitting until every student has one. This is why the check below is studentsNeeded ≤ m rather than == m.

Approach 1: Brute force, try every limit

Intuition. The maximum load cannot be smaller than the thickest book (max), because that book must land on someone. It never needs to exceed the total number of pages (sum), the load when one student takes everything. A larger limit never needs more students, so scanning limits from max upwards and stopping at the first one that needs at most m students yields the minimum.

Algorithm.

  1. If m > n, return -1.
  2. Compute max and sum of pages.
  3. For limit = max, max + 1, ..., sum: if studentsNeeded(pages, limit) ≤ m, return limit.
  4. Return sum (never reached: limit = sum always needs one student).
static int bruteForce(int[] pages, int m) {
    int n = pages.length;
    if (m > n) return -1;
    int max = 0, sum = 0;
    for (int p : pages) { max = Math.max(max, p); sum += p; }
    for (int limit = max; limit <= sum; limit++) {
        if (studentsNeeded(pages, limit) <= m) return limit;
    }
    return sum;
}

Complexity. Time O(n * (sum - max)): the range of limits can reach 10^11 with the stated constraints, each checked in O(n). Space O(1). Correct but unusable at scale.

Approach 2: Optimal, binary search on the limit

Intuition. Let ok(limit) be “the greedy scan needs at most m students”. If ok(limit) holds, then ok(limit + 1) holds too: the same blocks still respect the bigger limit. So over limit = max, ..., sum the predicate reads F F ... F T T ... T, and the answer is the first T. Binary search: when mid is feasible, record it and look for a smaller limit; otherwise look larger.

Algorithm.

  1. If m > n, return -1.
  2. Compute max and sum; set lo = max, hi = sum, ans = sum.
  3. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If studentsNeeded(pages, mid) ≤ m: ans = mid, hi = mid - 1.
    • Else: lo = mid + 1.
  4. Return ans.
static int optimal(int[] pages, int m) {
    int n = pages.length;
    if (m > n) return -1;
    int max = 0, sum = 0;
    for (int p : pages) { max = Math.max(max, p); sum += p; }
    int lo = max, hi = sum, ans = sum;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (studentsNeeded(pages, mid) <= m) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on pages = [12, 34, 67, 90], m = 2 (max = 90, sum = 203):

lo hi mid greedy blocks students ≤ 2? ans next
90 203 146 [12,34,67] [90] 2 yes 146 [90, 145]
90 145 117 [12,34,67] [90] 2 yes 117 [90, 116]
90 116 103 [12,34] [67] [90] 3 no 117 [104, 116]
104 116 110 [12,34] [67] [90] 3 no 117 [111, 116]
111 116 113 [12,34,67] [90] 2 yes 113 [111, 112]
111 112 111 [12,34] [67] [90] 3 no 113 [112, 112]
112 112 112 [12,34] [67] [90] 3 no 113 [113, 112] stop

Result 113.

Complexity. Time O(n log(sum)): sum ≤ 10^11 means about 37 iterations of an O(n) scan. Space O(1).

A note on sum and long

With n = 10^5 books of 10^6 pages, sum is 10^11, which does not fit in an int. The code above keeps sum, lo, hi and mid as int, which is correct for the typical judge limits (sum ≤ 10^9) and for every test in the Java file. If your constraints allow sum beyond 2^31 - 1, change those four variables and the return type to long; the logic does not change. The running load inside studentsNeeded is already a long.

Edge cases and pitfalls