Book Allocation Problem

The problem, simply

You get a row of n books. Book i has books[i] pages. You also get m students.

Give every book to exactly one student. Each student gets at least one book, and the books a student gets must sit next to each other on the shelf. Some student will read the most pages. Make that biggest load as small as possible and give it back. If there are more students than books, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

The answer is at least the biggest book (someone has to read it) and at most the sum of all pages (one student reads everything). Try every limit in that range, from small to big. The first limit that works is the answer.

To check one limit, hand out books greedily:

1. Start with student 1 and a load of 0.
2. For each book, if adding it would push the load past the limit, start the next student with this book.
3. Count the students you needed. The limit works if that count is at most m.

Filling each student as much as allowed is never worse, because it leaves the fewest books for the rest.

class Solution {
    // How many students do we need if nobody may read more than limit?
    int studentsNeeded(int[] books, int limit) {
        int students = 1, load = 0;
        for (int pages : books) {
            if (load + pages > limit) {   // this book does not fit, next student
                students++;
                load = 0;
            }
            load += pages;
        }
        return students;
    }

    public int findPages(int[] books, int m) {
        if (m > books.length) return -1;
        int lo = 0, hi = 0;
        for (int pages : books) {
            lo = Math.max(lo, pages);    // someone must read the biggest book
            hi += pages;                 // one student could read them all
        }
        for (int limit = lo; limit <= hi; limit++) {
            if (studentsNeeded(books, limit) <= m) return limit;
        }
        return hi;
    }
}

How long it takes: each check walks all n books, and we may try sum - max limits. With millions of pages that is far too slow: O(n * (sum - max)). Extra room: O(1).

Way 2: the clever way

Look at the limits in order: small limits all fail, and once a limit works, every bigger limit works too. So the row of answers looks like no, no, no, yes, yes, yes. Find the first yes with binary search on the answer.

1. lo = the biggest book, hi = the total pages.
2. Try the middle limit mid with the greedy check.
3. If it works, remember it and try smaller: hi = mid - 1.
4. If it needs too many students, try bigger: lo = mid + 1.
5. When lo passes hi, the remembered limit is the answer.

In the animation the bottom row is every limit we could answer. Limits marked rejected are too small, limits marked done are known to work. The bars show how the greedy check cuts the shelf into runs.

class Solution {
    int studentsNeeded(int[] books, int limit) {
        int students = 1, load = 0;
        for (int pages : books) {
            if (load + pages > limit) {
                students++;
                load = 0;
            }
            load += pages;
        }
        return students;
    }

    public int findPages(int[] books, int m) {
        if (m > books.length) return -1;
        int lo = 0, hi = 0;
        for (int pages : books) {
            lo = Math.max(lo, pages);
            hi += pages;
        }
        int best = hi;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (studentsNeeded(books, mid) <= m) {
                best = mid;          // it works, try a smaller limit
                hi = mid - 1;
            } else {
                lo = mid + 1;        // too strict, allow more pages
            }
        }
        return best;
    }
}

How long it takes: about log(sum - max) guesses (around 40 even for huge totals), each walking the books once: O(n log(sum - max)). Extra room: O(1).

Watch out for

• More students than books: return -1 before searching. The greedy check would happily say "fewer students needed", which is not allowed because each student needs a book.
• Using fewer students than m is fine. If a limit works with fewer students, you can always split a run to give the extra students one book each.
• The total pages can pass two billion. Use long for hi and the load if pages are large.
• The books must stay in order. Sorting them first changes the problem.

What interviewers ask next

• Painter's partition and "Split Array Largest Sum" (LeetCode 410) are this exact problem with new names. Ship packages within D days (LeetCode 1011) is too.
• Can you print the split, not just the number? Run the greedy check once more with the final limit and record where each student starts.
• Can dynamic programming solve it? Yes: dp[i][k] is the best answer for the first i books and k students. It costs O(n^2 * m), much slower than binary search.
• What if books can go in any order? Then it becomes a load balancing problem, which is much harder (NP-hard). A good greedy is to give the biggest remaining book to the least loaded student.

Remember this

Grown-up words: the guessing game is binary search on the answer, the no then yes row is a monotonic predicate, handing out books from the left is the greedy feasibility check, and the runs of books are contiguous partitions.