0875. Koko Eating Bananas
If we set l < r and r = m
state n-1
3 4 5 6 7
l r
m
state n
3 4 5 6 7
l
r
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1;
int r = *max_element(piles.begin(), piles.end());
int m;
long long hours;
while(l <= r){
m = l + (r - l) / 2;
hours = 0;
for(int& pile : piles){
hours += ((pile / m) + (pile % m != 0));
}
if(hours == h){
r = m - 1;
} else if(hours > h){
l = m + 1;
} else {
r = m - 1;
}
}
return l;
}
};
If we set l <= r and r = m - 1,
state n-2
3 4 5 6 7
l r
m
state n-1
3 4 5 6 7
l
r
m
state n
3 4 5 6 7
l r
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1;
int r = *max_element(piles.begin(), piles.end());
int m;
int hours;
while(l < r){
m = l + (r - l) / 2;
hours = 0;
for(int& pile : piles){
hours += ((pile / m) + (pile % m != 0));
}
if(hours == h){
r = m;
} else if(hours > h){
l = m + 1;
} else {
r = m;
}
}
return l;
}
};