Allocate Minimum Number of Pages

Given an array of integers where each element represents the number of pages in a book, and m is the number of students, the task is to allocate books to each student so that the maximum number of pages assigned to a student is minimized. Each student gets at least one book, and the books are assigned in a contiguous order.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [12, 34, 67, 90]
m = 2
Output: 113
Explanation: The books can be allocated as [12, 34, 67] and [90] to two students, where the maximum pages any student has is 113.

Example 2:
Input:
arr = [10, 20, 30, 40]
m = 2
Output: 60
Explanation: The books can be allocated as [10, 20, 30] and [40], with a maximum of 60 pages for any student.

Example 3:
Input:
arr = [10, 5, 20, 10]
m = 3
Output: 20
Explanation: The books can be allocated as [10, 5], [20], and [10], with a maximum of 20 pages.

Approach to allocate the minimum number of pages

  1. Binary Search for Optimal Page Allocation:
    • Set the search range for the minimum pages using low as the maximum single book’s pages (since each student must get at least one book) and high as the sum of all pages (the case where one student gets all books).
  2. Check Feasibility of Mid Value:
    • Use a helper function to check if it’s possible to allocate books such that no student gets more than mid pages:
      • Traverse through the books, accumulating pages for the current student.
      • If the pages exceed mid, allocate the next set of pages to a new student and continue. If the number of students exceeds m, the allocation is not possible with the current mid.
  3. Adjust Search Range Based on Feasibility:
    • If allocation is feasible, try with a smaller value to minimize the pages by setting high = mid - 1.
    • If not feasible, increase the pages by setting low = mid + 1.

C++ Program to Allocate Minimum Number of Pages

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

// Helper function to check if a given max pages is feasible
bool isFeasible(const vector<int>& arr, int n, int m, int maxPages) {
    int studentsRequired = 1, currentPages = 0;

    for (int pages : arr) {
        if (currentPages + pages > maxPages) {
            studentsRequired++;
            currentPages = pages;
            if (studentsRequired > m) {
                return false;
            }
        } else {
            currentPages += pages;
        }
    }

    return true;
}

// Function to find the minimum number of pages
int findMinPages(const vector<int>& arr, int m) {
    if (arr.size() < m) return -1;

    int low = *max_element(arr.begin(), arr.end());
    int high = accumulate(arr.begin(), arr.end(), 0);
    int result = high;

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

        if (isFeasible(arr, arr.size(), m, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

int main() {
    vector<int> arr = {12, 34, 67, 90};
    int m = 2;
    cout << "Minimum pages: " << findMinPages(arr, m) << endl;
    return 0;
}

Java Program to Allocate Minimum Number of Pages

java
import java.util.*;

public class AllocateMinimumPages {

    // Helper function to check if a given max pages is feasible
    private static boolean isFeasible(int[] arr, int n, int m, int maxPages) {
        int studentsRequired = 1, currentPages = 0;

        for (int pages : arr) {
            if (currentPages + pages > maxPages) {
                studentsRequired++;
                currentPages = pages;
                if (studentsRequired > m) {
                    return false;
                }
            } else {
                currentPages += pages;
            }
        }

        return true;
    }

    // Function to find the minimum number of pages
    public static int findMinPages(int[] arr, int m) {
        if (arr.length < m) return -1;

        int low = Arrays.stream(arr).max().getAsInt();
        int high = Arrays.stream(arr).sum();
        int result = high;

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

            if (isFeasible(arr, arr.length, m, mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {12, 34, 67, 90};
        int m = 2;
        System.out.println("Minimum pages: " + findMinPages(arr, m));
    }
}

Python Program to Allocate Minimum Number of Pages

python
# Helper function to check if a given max pages is feasible
def is_feasible(arr, m, max_pages):
    students_required = 1
    current_pages = 0

    for pages in arr:
        if current_pages + pages > max_pages:
            students_required += 1
            current_pages = pages
            if students_required > m:
                return False
        else:
            current_pages += pages

    return True

# Function to find the minimum number of pages
def find_min_pages(arr, m):
    if len(arr) < m:
        return -1

    low, high = max(arr), sum(arr)
    result = high

    while low <= high:
        mid = (low + high) // 2

        if is_feasible(arr, m, mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1

    return result

# Example usage
if __name__ == "__main__":
    arr = [12, 34, 67, 90]
    m = 2
    print("Minimum pages:", find_min_pages(arr, m))

Time Complexity:

  • O(n log S): Where n is the number of books and S is the range of the sum of pages. The binary search takes log S steps, and each step requires a scan of n books.

Space Complexity:

  • O(1): Only a constant amount of extra space is used for variables and the helper function, regardless of the input size.

DSA

1793

722

Related Articles