[Question]: There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8 Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5 Output: 30
// TC: O(n log k)
// O(n)(checkHours) * O(log k)(binary search where k = piles(max))
// SC: O(1) only a few integers are stored.
func checkHours(_ piles: [Int], _ k: Int, _ limit: Int) -> Bool {
var hours = 0
for pile in piles {
hours += Int(ceil(Double(pile) / Double(k)))
if hours > limit {// If hour limit exceeds means discard right half of array
return false
}
}
return hours <= limit
}
func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
// Define the binary search space,
// 1...max(piles) in this case.
var left = 1, right = Int.min
for pile in piles {
right = max(right, pile)
}
while left <= right {
let mid = (left + right) / 2
if checkHours(piles, mid, h) {
// Koko eats too many bananas.
// Encourage Koko to eat less bananas per hour.
right = mid - 1
// Discard right half of array
} else {
// Koko doesn't eat enough banans.
// Ask Koko to eat one more banana per hour.
left = mid + 1
// Discard left half of array
}
}
return left
}
let v = [3,6,7,11]
let h = 8
let ans = minEatingSpeed(v, h)
print("Koko should eat at least ", ans, " bananas/hr.")// 4#Approach 2: Using reduce
func minEatingSpeed1(_ piles: [Int], _ h: Int) -> Int {
var (l, r) = (1, piles.max()!)
while l < r{
var k = (l + r) / 2
let hrs = piles.reduce(0){return $0 + ($1 + k - 1)/k}
(l, r) = hrs <= h ? (k-1, k) : (k+1, r)
}
return l
}