Allocate Minimum Pages GFG problem
You are given an array arr[] of integers, where each element arr[i] represents the number of pages in the ith book. You also have an integer k representing the number of students. The task is to allocate books to each student such that:
Each student receives atleast one book.
Each student is assigned a contiguous sequence of books.
No book is assigned to more than one student.
The objective is to minimize the maximum number of pages assigned to any student. In other words, out of all possible allocations, find the arrangement where the student who receives the most pages still has the smallest possible maximum.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).
Examples:
Input: arr[] = [12, 34, 67, 90], k = 2
Output: 113
Explanation: Allocation can be done in following ways:
[12] and [34, 67, 90] Maximum Pages = 191
[12, 34] and [67, 90] Maximum Pages = 157
[12, 34, 67] and [90] Maximum Pages = 113.
Therefore, the minimum of these cases is 113, which is selected as the output.
Input: arr[] = [15, 17, 20], k = 5
Output: -1
Explanation: Allocation can not be done.
Input: arr[] = [22, 23, 67], k = 1
Output: 112
// { Driver Code Starts
// Initial Template for Java
import java.io.*;
import java.util.*;
class GFG {
public static void main(String[] args) throws IOException {
// Reading input using BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Number of test cases
int tc = Integer.parseInt(br.readLine().trim());
// Process each test case
while (tc-- > 0) {
// Read array of books (pages)
String[] str = br.readLine().trim().split(" ");
int[] a = new int[str.length];
for (int i = 0; i < str.length; i++) {
a[i] = Integer.parseInt(str[i]);
}
// Read number of students (k)
String[] nk = br.readLine().trim().split(" ");
int k = Integer.parseInt(nk[0]);
// Create Solution object and call findPages method
Solution sln = new Solution();
int ans = sln.findPages(a, k);
// Output the result
System.out.println(ans);
System.out.println("~");
}
}
}
// } Driver Code Ends
// Back-end complete function Template for Java
class Solution {
// Method to find the minimum weight capacity of the ship
public static int findPages(int[] arr, int k) {
// Edge case: If more students than books, it's impossible to allocate
if (k > arr.length) return -1;
// Initialize binary search boundaries
int low = getMax(arr); // Minimum capacity is at least the largest book
int high = maxsum(arr); // Maximum capacity is the sum of all books
int result = 0; // To store the result (minimum capacity)
// Perform binary search for the optimal capacity
while (low <= high) {
int mid = low + (high - low) / 2; // Middle value of the current range
int studentcount = 1; // We start with 1 student
int pagecount = 0; // Pages allocated to the current student
// Try to allocate books to students
for (int page : arr) {
// If adding the current book does not exceed the capacity (mid)
if (pagecount + page <= mid) {
pagecount += page; // Add the book to the current student
} else {
studentcount++; // Need to allocate to a new student
pagecount = page; // Start with the current book for the new student
}
// If a single book is larger than mid, we cannot allocate it
if (page > mid) {
studentcount = k + 1; // Force an invalid state (no solution)
break;
}
}
// If the number of students used is less than or equal to k, we have a valid solution
if (studentcount <= k) {
result = mid; // Save the current valid capacity
high = mid - 1; // Try for a smaller capacity
} else {
low = mid + 1; // Need more capacity to fit all books
}
}
// Return the result (minimum capacity needed)
return result;
}
// Helper function to get the maximum book size (largest number of pages in a book)
static int getMax(int[] arr) {
int maxi = Integer.MIN_VALUE;
for (int page : arr) {
maxi = Math.max(page, maxi); // Find the largest page count
}
return maxi;
}
// Helper function to calculate the total sum of all pages (maximum capacity possible)
static int maxsum(int[] arr) {
int sum = 0;
for (int page : arr) {
sum += page; // Sum of all pages
}
return sum;
}
}
Comments
Post a Comment