-
Notifications
You must be signed in to change notification settings - Fork 0
/
allocate minimum number ofpages.java
50 lines (50 loc) · 1.53 KB
/
allocate minimum number ofpages.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
import java.util.*;
//to check if allocation of books among given students is possible.
class TUF {
static boolean isPossible(ArrayList < Integer > A, int pages, int students) {
int cnt = 0;
int sumAllocated = 0;
for (int i = 0; i < A.size(); i++) {
if (sumAllocated + A.get(i) > pages) {
cnt++;
sumAllocated = A.get(i);
if (sumAllocated > pages) return false;
} else {
sumAllocated += A.get(i);
}
}
if (cnt < students) return true;
return false;
}
public static int books(ArrayList < Integer > A, int B) {
if (B > A.size()) return -1;
int low = A.get(0);
int high = 0;
for (int i = 0; i < A.size(); i++) {
high = high + A.get(i);
low = Math.min(low, A.get(i));
}
int res = -1;
while (low <= high) {
int mid = (low + high) >> 1;
//cout << low << " " << high << " " << mid << endl;
if (isPossible(A, mid, B)) {
res = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
// return res -> this is also correct
return low;
}
public static void main(String args[]) {
ArrayList < Integer > A = new ArrayList < > ();
A.add(12);
A.add(34);
A.add(67);
A.add(90);
int B = 2;
System.out.println("Minimum Possible Number is " + books(A, B));
}
}