Description
You are given a list of integers piles and an integer k. piles[i] represents the number of bananas on pile i. On each hour, you can choose any pile and eat r number of bananas in that pile. If you pick a pile with fewer than r bananas, it still takes an hour to eat the pile.
Return the minimum r required such that you can eat all the bananas in less than or equal to k hours.
Constraints:
-
n ≤ 100,000wherenis the length ofpiles n ≤ k
Example 1
Input
piles = [6, 4, 3]
k = 5
Output
3
Explanation
At r = 3 bananas per hour, we can eat the first pile in 2 hours, eat the second in 2 hours, and eat the last pile in 1 hour.
Intuition
binary search
- l: at least eat
1banana - r: the maximum number of bananas in a pile
Implementation
import java.util.*;
class Solution {
public int solve(int[] piles, int k) {
int n = piles.length;
int l = 1, r = Integer.MIN_VALUE;
for (int pile : piles) {
r = Math.max(pile, r);
}
while (l < r) {
int mid = l + r >> 1;
if (canEat(mid, piles, k)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private boolean canEat(int r, int[] piles, int k) {
int hours = 0;
for (int pile : piles) {
hours += Math.ceil((float) pile / r);
}
return hours <= k;
}
}
Time Complexity
- Time: O(nlogn)
- Space: O(1)
Top comments (0)