Book Allocation Promblem in Binary search

Problem Statement:

Given an array of books, where each book has a certain number of pages, and a number of students, you need to allocate books in a way that minimizes the maximum number of pages assigned to a student. Each student must be allocated at least one book.

Approach:

1. Define the Problem:

   • Understand that the goal is to minimize the maximum number of pages assigned to a student.

2. Set the Search Space:

   • Use binary search to set the search space. The minimum possible value is the maximum number of pages in a single book, and the maximum possible value is the sum of all pages in all books.

3. Implement the Check Function:

   • Write a function that takes the current mid value (the candidate for the maximum pages assigned to a student) and checks if it's possible to allocate books in a way that satisfies the problem constraints. This function will be used in the binary search.

4. Binary Search:

   • Perform binary search within the defined search space. Update the search space based on whether it is possible to allocate books with a given maximum pages to each student.

5. Optimal Solution:

   • At the end of the binary search, you will have the optimal solution, which is the minimum maximum pages assigned to a student.

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

using namespace std;

bool is_valid(const vector<int>& arr, int n, int k, int mid) {
    int students_required = 1;
    int current_pages = 0;

    for (int i = 0; i < n; ++i) {
        if (arr[i] > mid) {
            return false;
        }

        if (current_pages + arr[i] > mid) {
            students_required++;
            current_pages = arr[i];
        } else {
            current_pages += arr[i];
        }
    }

    return students_required <= k;
}

int allocate_books(const vector<int>& arr, int k) {
    int n = arr.size();
    int low = *max_element(arr.begin(), arr.end());
    int high = accumulate(arr.begin(), arr.end(), 0);
    int result = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (is_valid(arr, n, k, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

int main() {
    vector<int> arr = {12, 34, 67, 90};
    int k = 2;

    int result = allocate_books(arr, k);

    cout << "Minimum pages allocated to a student: " << result << endl;

    return 0;
}