Lecture 62 :- Book Allocation Problem

The Book Allocation Problem is a classic optimization problem related to book distribution. It is also known as the "Allocate Minimum Number of Pages" problem. The problem statement is as follows:

You are given an array of N books, where the i-th book has A[i] number of pages. You have to allocate these books to M students in such a way that each student gets a contiguous subarray of books, and the maximum number of pages assigned to a student is minimized. Each student must be allocated at least one book.

To solve this problem, we can use binary search to find the minimum number of pages that can be allocated to a student. We will set the search space to be the range from the maximum number of pages in the array to the sum of all the pages in the array. Then, we will check if it is possible to allocate the books in a way that the maximum number of pages assigned to a student is less than or equal to the mid value (the value we are currently searching for). If it is possible, we try to minimize this maximum value by moving to the left half of the search space. Otherwise, we move to the right half.

Here's the C++ implementation of the Book Allocation Problem:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> bool isPossible(std::vector<int>& books, int numStudents, int maxPages) {    int students = 1;    int pagesAllocated = 0;    for (int i = 0; i < books.size(); i++) {        if (books[i] > maxPages) {            return false;        }        if (pagesAllocated + books[i] > maxPages) {            students++;            pagesAllocated = books[i];        } else {            pagesAllocated += books[i];        }    }    return students <= numStudents; } int allocateBooks(std::vector<int>& books, int numStudents) {    int n = books.size();    int totalPages = 0;    int maxPages = 0;    for (int i = 0; i < n; i++) {        totalPages += books[i];        maxPages = std::max(maxPages, books[i]);    }    int left = maxPages;    int right = totalPages;    int result = -1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (isPossible(books, numStudents, mid)) {            result = mid;            right = mid - 1;        } else {            left = mid + 1;        }    }    return result; } int main() {    std::vector<int> books = {12, 34, 67, 90};    int numStudents = 2;    int minMaxPages = allocateBooks(books, numStudents);    std::cout << "Minimum maximum pages allocated: " << minMaxPages << std::endl;    return 0; }

Example Output:

yamlCopy code

Minimum maximum pages allocated: 113

In this code, the isPossible function checks if it is possible to allocate books in a way that the maximum number of pages assigned to a student is less than or equal to maxPages. The allocateBooks function uses binary search to find the minimum maximum pages that can be allocated to a student. The time complexity of this algorithm is O(N * log(sum)), where N is the number of books and sum is the sum of all pages in the array.