Binary Search Based : Allotting books

Binary search based problem : Allotting all the library books to N students and return the number of pages with a criteria.

Criteria 1 : Allot all the books.
Criteria 2 : Allot the books in continuous order.
Criteria 3 : Allot the books such that the maximum number of pages of books issued to a student is minimum.

Reference : Interview Bit Problem Allot Books

Binary Search looks for a value in a sorted array. It compares the middle number of the array with the searched value. If the middle number equals the searched value, the position of the middle number is returned. If the middle number is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched using binary search.

Time complexity of the binary search algorithm for finding the smallest number in a sorted rotated array : Log ( N )

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

C++ : Binary search use case : Allotting all the library books to N student with a criteria. Implemented in C++11

#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) {
                allocated_pages = pages;

                /* The allocation of allocated_pages > maxpages being invalid cannot be done for any student */
                if (allocated_pages > maxpages)
                    return false;
                
                student_num++;
            }
        }
    }

    /* If student number is less than total student, 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) {

    if (books.size() == 0)
        return 0;
    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 © 2020, Algotree.org.
All rights reserved.