Binary Search : Allocate books

Binary search problem: Allocate library books with a minimum of a maximum number of pages.

Given:
N number of books are available. ( 1 . . . N )
Each book ‘x’ from 1 .. N has B [ x ] number of pages
There are ‘S’ students.

Book allocation criteria
Criteria 1 : Allocate all the books.
Criteria 2 : Each student is issued at least one book.
Criteria 3 : Allocate the books in continuous order.
Criteria 4 : Allocate the books such that the maximum number of pages of books issued to a student is minimum.


Example: Consider 4 books with pages [ 10 , 32 , 70, 88 ]
Number of students : 2
Possible allocations as below:
Allocation 1 -> S1 : ( 10 ) S2 : ( 32 + 70 + 88 ) Max pages = 190
Allocation 2 -> S1 : ( 10 + 32 ) S2 : ( 70 + 88 ) Max pages = 158
Allocation 3 -> S1 : ( 10 + 32 + 70 ) S2 : ( 88 ) Max pages = 112

From the above 4 allocations, the minimum of max pages after the allocation is 112.


Idea for solving the book allocation problem using binary search

Case a) If the number of books is less than the number of students, then at least 1 student is not issued any book.

Case b) If the number of books equals number of students, then each student gets a book. Thus the minimum of maximum pages allocated is maximum of ( B[1], B[2], … B[N] ).

Use binary search to find the minimum of the maximum number of pages
Example :
Consider 4 books with pages [ 1, 2, 3, 4 ], and 2 students.
Choose a very large number (INT_MAX) say 100 (maxpages) that we can allocate to a student.

Binary_Search_Allocate_Books

Beg End Mid (Max Pages) Student 1 Student 2 Number of students with books
0 100 50 1 + 2 + 3 + 4 (All 4 books) 0 (No books) 1 (Student 1). More pages have got allocated to Student 1.
So continue binary search with smaller number of max pages i.e (50-1) / 2
0 49 24 1 + 2 + 3 + 4 (All 4 books) 0 (No books) 1 (Student 1). More pages have got allocated to Student 1.
So continue binary search with smaller number of max pages i.e 24-1 / 2
0 23 11 1 + 2 + 3 + 4 (All 4 books) 0 (No books) 1 (Student 1). More pages have got allocated to Student 1.
So continue binary search with smaller number of max pages i.e 11-1 / 2
0 10 5 1 + 2 (2 books) 3 + 4 (2 books) Student 2 now has more than (Max Pages i.e 5) so try with a bigger number.
6 10 8 1 + 2 + 3 (3 books) 4 (1 book) 2 (Student 1, Student 2). 8 pages is valid but still try with a lower number of max pages.
6 7 6 1 + 2 + 3 (3 books) 4 (1 book) 2 (Student 1, Student 2). 6 pages is valid but still try with a lower number of max pages.

Since beg <= end becomes invalid, the search terminates. Thus we have 6 as the minimum of maximum pages that can be allocated to a student.


Time complexity : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?

C++ program for allotting all the library books to N student using binary search.

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

bool CanAllocate(vector<int>& books, int& maxpages, int students) {

    int student_num = 1;
    int allocated_pages = 0;

    for (const auto& pages : books) {

        if (allocated_pages <= maxpages) {
            allocated_pages += pages;
            /* Current allocation exceeds the maxpages, so this
               allocation may go to the next student.*/
            if (allocated_pages > maxpages) {
                int next_student_allocated_pages = pages;

                /* If the next_student_allocated_pages > maxpages, then the allocation is invalid and 
                   cannot be done for the next student. So try with bigger page allocation (maxpages)*/
                if (next_student_allocated_pages > maxpages)
                    return false;

                // Allocation is valid so proceed.
                student_num++;
                allocated_pages = next_student_allocated_pages;
            }
        }
    }

    /* If student number is less than total students, more pages have got allocated to
       the students. We can start with less number of pages in the next go.
       So continue the binary search */
    if (student_num <= students)
        return true;

    return false;
}

int IssueBooks(vector<int>& books, int students) {

    // Each student should be alloted atleast 1 book.
    if (books.size() < students)
        return -1;

    if (books.size() == students)
        return *max_element(books.begin(), books.end());

    int end = INT_MAX;
    int beg = 0;
    int possible_pages = 0;

    while (beg <= end) {
        int maxpages = beg + (end - beg)/2;
        if (CanAllocate(books, maxpages, students)) {
            possible_pages = maxpages;
            end = maxpages - 1;
        } else {
            beg = maxpages + 1;
        }
    }
    return possible_pages;
}

int main() {

    vector<int> books = {10, 32, 70, 88};

    // Student(s) 1  1:(10 + 32 + 70 + 88)
    // Student(s) 2  1:(10 + 32 + 70), 2:(88)
    // Student(s) 3  1:(10 + 32) 2:(70), 3:(88)
    // Student(s) 4  1:(10), 2:(32), 3:(70), 4:(88)

    int students = 1;
    cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students)  << endl;

    students = 2;
    cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students)  << endl;

    students = 3;
    cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students)  << endl;

    students = 4;
    cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students)  << endl;

    return 0;
}

Output

Maximum possible pages allocated to 1 : 200
Maximum possible pages allocated to 2 : 112
Maximum possible pages allocated to 3 : 88
Maximum possible pages allocated to 4 : 88

Copyright (c) 2020, Algotree.org.
All rights reserved.