☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Allocate Minimum Number of Pages

Hard TUF ID 2766 SDE

Java source ↗ Edit this article ↗

Problem

There are n books in a row; book i has pages[i] pages. You must hand them out to m students under three rules:

Among all valid allocations, minimise the number of pages read by the busiest student, and return that minimum. If there are more students than books, no valid allocation exists: return -1.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ pages[i] ≤ 10^9. The total can reach 10^14, so sums need a long.

Example 1

pages = [12, 34, 67, 90], m = 2
answer = 113        // [12, 34, 67] | [90]; the other splits give 157 and 191

Example 2

pages = [25, 46, 28, 49, 24], m = 4
answer = 71         // [25, 46] | [28] | [49] | [24]

The key reformulation

Searching over allocations directly is hopeless: there are C(n-1, m-1) ways to place the cut points. Flip the question. Instead of “what is the best allocation?”, ask a yes/no question about a number:

Given a limit L, can the books be split so that nobody reads more than L pages?

That question has two properties that make it easy.

It can be answered greedily in O(n). Walk through the books and give each one to the current student while their total stays within L; when the next book would overflow, start a new student. Filling each student as much as possible is safe: by induction, after its first j students the greedy has placed at least as many books as the first j students of any other split within L, so it never needs more students than that split. The number of students this uses is the minimum possible for L.

It is monotonic. If a limit L works, every bigger limit also works with the same split. So the limits read “no, no, …, no, yes, yes, …”, and the answer is the first “yes”.

Why compare the greedy count with ≤ m and not == m? If the greedy needs fewer than m students, we can split some student’s block further: every block has at least one book and there are at least m books, so we can keep peeling single books off multi-book blocks until exactly m students are busy. Splitting never increases anyone’s total.

The answer always lies between two natural bounds: at least max(pages) (someone has to read the largest book) and at most sum(pages) (one student reads everything).

static int studentsNeeded(int[] pages, long maxPages) {
    int students = 1;
    long current = 0;
    for (int p : pages) {
        if (current + p > maxPages) {                  // this book does not fit: start the next student
            students++;
            current = p;
        } else {
            current += p;
        }
    }
    return students;
}

The helper assumes maxPages ≥ every single book. Below that bound a book cannot fit anywhere, yet the code would still give it a student of its own and report a misleadingly small count. Both approaches start their search at max(pages), so this never happens.

Approach 1: Brute force, try every limit in order

Intuition. Test the limits max, max + 1, max + 2, ... one by one. By monotonicity, the first one the greedy accepts is the answer.

Algorithm.

  1. If m > n, return -1.
  2. Compute lo = max(pages) and hi = sum(pages).
  3. For limit from lo to hi: if studentsNeeded(pages, limit) ≤ m, return limit.
static long bruteForce(int[] pages, int m) {
    if (m > pages.length) return -1;                   // someone would get no book
    long lo = 0, hi = 0;
    for (int p : pages) {
        lo = Math.max(lo, p);
        hi += p;
    }
    for (long limit = lo; limit <= hi; limit++) {
        if (studentsNeeded(pages, limit) <= m) return limit;
    }
    return -1;
}

Complexity. Time O(n · (sum - max)): up to sum - max + 1 limits, each checked in O(n). With page counts up to 10^9, that range is astronomically large. Space O(1).

Approach 2: Optimal, binary search on the answer

Intuition. A monotonic yes/no question over a sorted range of candidates is exactly what binary search solves. Probe the middle limit. If it is feasible, the answer is that limit or something smaller, so keep it in range (hi = mid). If not, the answer is strictly larger (lo = mid + 1). When lo == hi, that single remaining value is the smallest feasible limit.

Algorithm.

  1. If m > n, return -1.
  2. lo = max(pages), hi = sum(pages).
  3. While lo < hi: mid = lo + (hi - lo) / 2. If studentsNeeded(pages, mid) ≤ m, set hi = mid, else lo = mid + 1.
  4. Return lo.
static long optimal(int[] pages, int m) {
    if (m > pages.length) return -1;
    long lo = 0, hi = 0;
    for (int p : pages) {
        lo = Math.max(lo, p);
        hi += p;
    }
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (studentsNeeded(pages, mid) <= m) hi = mid;  // feasible: the answer is mid or smaller
        else lo = mid + 1;                              // infeasible: the answer is bigger than mid
    }
    return lo;
}

Dry run on Example 1 (lo = 90, hi = 203, m = 2):

lo hi mid greedy split for mid students action
90 203 146 [12, 34, 67] [90] 2 hi = 146
90 146 118 [12, 34, 67] [90] 2 hi = 118
90 118 104 [12, 34] [67] [90] 3 lo = 105
105 118 111 [12, 34] [67] [90] 3 lo = 112
112 118 115 [12, 34, 67] [90] 2 hi = 115
112 115 113 [12, 34, 67] [90] 2 hi = 113
112 113 112 [12, 34] [67] [90] 3 lo = 113

The loop ends with lo = hi = 113. Notice that the answer is always the total of some student’s block in the optimal split (here 12 + 34 + 67), because the smallest feasible limit cannot sit strictly between achievable totals.

Complexity. Time O(n log(sum)): about log2(10^14) ≈ 47 greedy passes. Space O(1).

Edge cases and pitfalls