Book Allocation Problem

Q: Is the Book Allocation Problem the same as Split Array Largest Sum?

Yes. Both cut an array into a fixed number of non-empty contiguous blocks and minimise the largest block sum, and the same binary search with the same greedy check solves both. The book version adds the -1 case.

Q: What is the time complexity of the Book Allocation Problem?

O(n log S) time and O(1) extra space, where n is the number of books and S the total page count. Each limit tried costs one pass over the books, and the search tries about log2 S limits: 29 on a shelf of 5 × 10^8 pages.

Q: When is it impossible to allocate the books?

Only when there are more students than books, since every student needs at least one book. With enough books, any block of two or more books can give its last book to a student with none until everyone has one.

MediumBinary search Greedy

+10

A shelf holds books in a fixed order, and pages[i] is the number of pages in book i. Share the books among students students: each student gets one unbroken run of neighbouring books, at least one book each, and every book goes to exactly one student. A student's load is the total number of pages they receive.

Return the smallest possible value of the heaviest load. If there are more students than books, return -1.

Function

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: the page count of each book, in shelf order
studentsinteger: the number of students who share the books
Returnsinteger: the smallest possible heaviest load, or -1 when there are more students than books

Constraints

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Return -1 when students > pages.length.

Examples

Input: pages = [25, 40, 15, 30, 50]students = 3
Output: 65
Explanation: Give out [25, 40], [15, 30] and [50]: loads 65, 45 and 50. A limit of 64 fails: the hand-out gives [25], [40, 15], [30], [50], four students.

Input: pages = [10, 20]students = 3
Output: -1
Explanation: Two books cannot give three students one book each, so the answer is -1.

Follow-up

Prove that the average share, rounded up, plus the thickest book is always a working limit. How many checks does that upper end save on a shelf of thin books?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There are too many ways to cut the shelf, but testing one page limit is cheap: hand out books in shelf order, moving to the next student when a book would pass the limit, and count the students. A higher limit never needs more students, so the limits that work form one run, and binary search finds where it starts.

Raise the page limit one page at a time

Correct, but does not finish on the largest tests

Intuition

Start at L = max(pages), since someone carries the thickest book, and raise L one page at a time until the greedy count fits in students. Every lower limit failed, so the first that fits is the answer. In the first example every limit from 50 to 64 needs four students and 65 needs three: 16 checks.

The answer can be the whole shelf: one student and 5000 books of 10^5 pages means about 5 × 10^8 limits, each a pass over 5000 books. In the time column, A is the answer and m the thickest book.

Algorithm

If students > pages.length, return -1.
Write the greedy count for a limit L: start with one student and a load of 0; when load + pages[i] > L, add a student and set the load to pages[i], otherwise add the book to the load.
Set L to the thickest book.
While the count for L is more than students, add 1 to L.
Return L.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

Binary search on the page limit

Intuition

The greedy count is the fewest students any sharing under L can use. Compared student by student with any other sharing, each greedy student stops only when the next book does not fit, so it ends at least as far along the shelf. Fewer students than you have is fine: a student holding two books can pass one to a student with none, and no load grows.

So L works exactly when the greedy count is at most students. Whatever works under L works under L+1, so binary search finds the first limit that works.

The range starts at the larger of max(pages) and the average share, total / students rounded up, since the heaviest load is at least both. The top is total. In the first example that is 54 to 160, and the search tries 107, 80, 67, 60, 64, 66 and 65.

Algorithm

If students > pages.length, return -1.
Add up total and find the thickest book. Set lo to the larger of the thickest book and (total + students - 1) / students, and hi = total.
While lo < hi, take mid = lo + (hi - lo) / 2.
Run the greedy count for mid. If it is at most students, set hi = mid; otherwise set lo = mid + 1.
Return lo.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

Pitfalls and edge cases

Skipping the -1 check. For [10, 20] and 3 students the greedy count at a limit of 20 is 2, so the search returns 20.
Starting the range at the average share alone. For [1, 9] and 2 students the average is 5, and there the greedy puts the 9 page book alone, counts 2 and returns 5.
Testing for exactly students. For [5, 5, 5, 5, 5, 5] and 4 students the answer is 10, where the greedy count is 3.
Sorting the books. [10, 1, 1, 10] with 2 students gives 11, but sorted to [1, 1, 10, 10] it gives 12.

Frequently asked questions3

Is the Book Allocation Problem the same as Split Array Largest Sum?

Yes. Both cut an array into a fixed number of non-empty contiguous blocks and minimise the largest block sum, and the same binary search with the same greedy check solves both. The book version adds the -1 case.

What is the time complexity of the Book Allocation Problem?

O(n log S) time and O(1) extra space, where n is the number of books and S the total page count. Each limit tried costs one pass over the books, and the search tries about log2 S limits: 29 on a shelf of 5 × 10^8 pages.

When is it impossible to allocate the books?

Only when there are more students than books, since every student needs at least one book. With enough books, any block of two or more books can give its last book to a student with none until everyone has one.

def allocateBooks(pages, students):
    # Write code here

Test #1

Test #2

Test #3

Arguments

pages = [25, 40, 15, 30, 50]
students = 3

Expected Output