Dare2Solve
In this problem, we need to determine the minimum eating speed that allows a person to finish eating all the piles of bananas within a given number of hours. The input consists of an array representing the piles of bananas and an integer h
representing the maximum hours available. The challenge is to find the minimum speed k
such that the person can eat all the bananas in h
hours or less.
The problem involves finding the smallest possible value of k
that satisfies the condition. A brute-force approach would test every possible value of k
, but this would be inefficient. Instead, we can use binary search to efficiently narrow down the possible values of k
. The binary search will allow us to find the minimum speed by repeatedly halving the search range until the optimal value is found.
Initialize the Search Space: Set the initial values for low
as 1 (the minimum speed) and high
as the maximum value in the piles
array (the maximum speed).
Binary Search: Perform binary search on the speed k
.
mid
as the average of low
and high
.h
hours using speed k = mid
.high
value to mid - 1
.low
value to mid + 1
.Check Function: A helper function checks if a given speed k
can finish all the piles within h
hours by iterating through the piles
array and calculating the total hours required.
Return the Result: Once the binary search completes, low
will contain the minimum eating speed required.
O(n log m)
, where n
is the number of piles and m
is the range of possible speeds (from 1 to the maximum number of bananas in a pile). The binary search runs in O(log m)
, and for each iteration, we check if the speed is valid in O(n)
.
O(1)
since we only use a few extra variables and no additional data structures.
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1;
int high = *max_element(piles.begin(), piles.end());
int ans = high; // Initialize ans with the maximum possible value
while (l <= high) {
int mid = l + (high - l) / 2;
if (canEatAll(piles, h, mid)) {
ans = mid;
high = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
private:
bool canEatAll(const vector<int>& piles, int h, int k) {
long long hours = 0; // Use long long to store the number of hours
for (int pile : piles) {
hours += (pile + k - 1) / k; // This is equivalent to ceil(pile / k)
if (hours > h) {
return false;
}
}
return true;
}
};
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = 1
high = max(piles)
ans = -1
def checkHrs(mid, piles):
hrs = 0
for pile in piles:
hrs += (pile + mid - 1) // mid # Equivalent to ceil(pile / mid)
return hrs
while l <= high:
mid = (l + high) // 2
hrs = checkHrs(mid, piles)
if hrs <= h:
ans = mid
high = mid - 1
else:
l = mid + 1
return ans
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1;
int high = Integer.MIN_VALUE;
for (int pile : piles) {
high = Math.max(high, pile);
}
int ans = high;
while (l <= high) {
int mid = l + (high - l) / 2;
if (canEatAllInTime(piles, h, mid)) {
ans = mid;
high = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
private boolean canEatAllInTime(int[] piles, int h, int k) {
int hrs = 0;
for (int pile : piles) {
// Using (pile + k - 1) / k is equivalent to ceil(pile / k) and prevents overflow
hrs += (pile + k - 1) / k;
if (hrs > h) {
return false; // Early exit if we already exceed hours
}
}
return hrs <= h;
}
}
var minEatingSpeed = function (piles, h) {
let l = 1
let high = Math.max(...piles)
let ans = -1
function checkHrs(mid, piles) {
let hrs = 0
console.log(mid)
for (let i = 0; i < piles.length; i++) {
hrs += Math.ceil(piles[i] / mid)
}
console.log(hrs, 'hrs')
return hrs
}
while (l <= high) {
let mid = Math.floor((l + high) / 2)
const hrs = checkHrs(mid, piles)
if (hrs <= h) {
ans = mid
high = mid - 1
}
else l = mid + 1
}
return ans
};