forked from abhimanyuiscoding/Hacktoberfest2022
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Book_Allocation.java
83 lines (67 loc) · 1.87 KB
/
Book_Allocation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Problem : https://practice.geeksforgeeks.org/problems/allocate-minimum-number-of-pages0937/1
// Solution :
public class Book_Allocation {
// Utility method to check if current minimum value
// is feasible or not.
static boolean isPossible(int arr[], int n, int m,
int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;
// iterate over all books
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
if (curr_sum > curr_min) {
studentsRequired++; // increment student
// count
curr_sum = arr[i]; // update curr_sum
}
}
return studentsRequired <= m;
}
// method to find minimum pages
static int findPages(int arr[], int n, int m)
{
int sum = 0;
// return -1 if no. of books is less than
// no. of students
if (n < m)
return -1;
// Count total number of pages
for (int i = 0; i < n; i++)
sum += arr[i];
// initialize start as arr[n-1] pages(minimum answer
// possible) and end as total pages(maximum answer
// possible)
int start = arr[n - 1], end = sum;
int result = Integer.MAX_VALUE;
// traverse until start <= end
while (start <= end) {
// check if it is possible to distribute
// books by using mid is current minimum
int mid = start + (end - start) / 2;
if (isPossible(arr, n, m, mid)) {
// update result to current distribution
// as it's the best we have found till now.
result = mid;
// as we are finding minimum so,
end = mid - 1;
}
else
// if not possible, means pages should be
// increased ,so update start = mid + 1
start = mid + 1;
}
// at-last return minimum no. of pages
return result;
}
// Driver Method
public static void main(String[] args)
{
int arr[] = { 12, 34, 67,
90 }; // Number of pages in books
int m = 2; // No. of students
System.out.println("Minimum number of pages = "
+ findPages(arr, arr.length, m));
}
}