-
Notifications
You must be signed in to change notification settings - Fork 42
/
KokoEatingBananas.java
136 lines (110 loc) · 3.91 KB
/
KokoEatingBananas.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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package LeetCodeJava.BinarySearch;
// https://leetcode.com/problems/koko-eating-bananas/
import java.util.Arrays;
public class KokoEatingBananas {
// V0
// IDEA : BINARY SEARCH (close boundary)
public int minEatingSpeed(int[] piles, int h) {
if (piles.length == 0 || piles.equals(null)){
return 0;
}
int l = 1; //Arrays.stream(piles).min().getAsInt();
int r = Arrays.stream(piles).max().getAsInt();
while (r >= l){
int mid = (l + r) / 2;
int _hour = getCompleteTime(piles, mid);
if (_hour <= h){
r = mid - 1;
}else{
l = mid + 1;
}
}
return l;
}
// V0
// IDEA : BINARY SEARCH (open boundary)
public int minEatingSpeed_2(int[] piles, int h) {
if (piles.length == 0 || piles.equals(null)){
return 0;
}
// https://stackoverflow.com/questions/1484347/finding-the-max-min-value-in-an-array-of-primitives-using-java
int l = 1; //Arrays.stream(piles).min().getAsInt();
int r = Arrays.stream(piles).max().getAsInt();
while (r > l){
int mid = (l + r) / 2;
int _hour = getCompleteTime(piles, mid);
//System.out.println("l = " + l + " r = " + r + " mid = " + mid + " _hour = " + _hour);
if (_hour <= h){
r = mid;
}else{
l = mid + 1;
}
}
return r;
}
private int getCompleteTime(int[] piles, int speed){
int _hour = 0;
for (int pile : piles) {
_hour += Math.ceil((double) pile / speed);
}
return _hour;
}
// V1
// IDEA : BRUTE FORCE
// https://leetcode.com/problems/koko-eating-bananas/editorial/
public int minEatingSpeed_3(int[] piles, int h) {
// Start at an eating speed of 1.
int speed = 1;
while (true) {
// hourSpent stands for the total hour Koko spends with
// the given eating speed.
int hourSpent = 0;
// Iterate over the piles and calculate hourSpent.
// We increase the hourSpent by ceil(pile / speed)
for (int pile : piles) {
hourSpent += Math.ceil((double) pile / speed);
if (hourSpent > h) {
break;
}
}
// Check if Koko can finish all the piles within h hours,
// If so, return speed. Otherwise, let speed increment by
// 1 and repeat the previous iteration.
if (hourSpent <= h) {
return speed;
} else {
speed += 1;
}
}
}
// V2
// IDEA : BINARY SEARCH
// https://leetcode.com/problems/koko-eating-bananas/editorial/
public int minEatingSpeed_4(int[] piles, int h) {
// Initialize the left and right boundaries
int left = 1, right = 1;
for (int pile : piles) {
right = Math.max(right, pile);
}
while (left < right) {
// Get the middle index between left and right boundary indexes.
// hourSpent stands for the total hour Koko spends.
int middle = (left + right) / 2;
int hourSpent = 0;
// Iterate over the piles and calculate hourSpent.
// We increase the hourSpent by ceil(pile / middle)
for (int pile : piles) {
hourSpent += Math.ceil((double) pile / middle);
}
// Check if middle is a workable speed, and cut the search space by half.
if (hourSpent <= h) {
right = middle;
} else {
left = middle + 1;
}
}
// Once the left and right boundaries coincide, we find the target value,
// that is, the minimum workable eating speed.
return right;
}
}