Back to Main
Learn DSA
Depth-First Search
Greedy Algorithms
Get Premium
Binary Search
Apple Harvest (Koko Eating Bananas)
medium
DESCRIPTION (credit Leetcode.com)
Bobby has an orchard of apple trees, and each tree has a certain number of apples on it.
Bobby wants to collect all the apples by the end of the day by collecting a fixed number of apples per hour. He can only harvest apples from one tree per hour - if he finishes collecting apples from a tree before the hour is up, he must wait until the next hour to move to the next tree.
- For example, if there are 3 apples on a tree and Bobby collects 1 apple per hour, it will take him 3 hours to finish collecting the apples on that tree.
- If he harvests 2 apples per hour, it will take him 2 hours to finish collecting all the apples on that tree (he waits until the hour is up even though he finishes early).
Write a function to determine the slowest rate of apples Bobby can harvest per hour to finish the job in at most 'h' hours. The input to the function is an array of integers representing the number of apples on each tree and an integer 'h' representing the number of hours Bobby has to finish the job within.
Example 1:
Input:
Output: 3
Explanation:
- 1 apple per hour: 3 hours for first tree, 6 hours the second tree, and 7 hours for third tree. This totals 16 hours, which is more than the 8 hours he has to finish the job. NOT VALID.
- 2 apples per hour: 2 + 3 + 4 = 9 hours, which is more than the 8 hours he has to finish the job. NOT VALID.
- 3 apples per hour: 1 + 2 + 3 = 6 hours, which is less than the 8 hours he has to finish the job. VALID.
- 4 apples per hour: 1 + 2 + 2 = 5 hours, which is less than the 8 hours he has to finish the job. VALID.
- 5 apples per hour: 1 + 2 + 2 = 5 hours, which is less than the 8 hours he has to finish the job. VALID.
Therefore, the minimum number of apples Bobby must harvest per hour to finish the job in 8 hours or less is 3.
Example 2:
Input:
Output: 25 (Bobby must harvest 25 apples per hour to finish in 5 hours or less)
Explanation
In this problem, we are trying to find the slowest rate at reach we can harvest all the apples in the orchard within the given time limit and the requirements of the problem.
Brute-Force Approach
One observation before starting to solve this problem:
- The slowest rate at which can harvest apples is 1.
- The fastest rate at which can harvest apples is equal to the maximum number of apples in the orchard, as going any faster than this will not change the time taken to harvest all the apples.
For example, if apples = [25, 9, 23, 8, 3], then going at rate any faster than 25 apples per hour will take the same time as going at 25 apples per hour.
The brute-force approach to this problem works similar to the explanation in the Example section above.
We'll start with a rate of 1, and calculate the time taken to harvest all the apples at this rate.
- If that time is less than or equal to the given time limit, then we've found the slowest rate at which we can harvest all the apples in the given time limit, so we return this rate.
- If the time taken is greater than the given time limit, then we increase the rate by 1 and repeat.
Calculating Time Taken
To calculate the time taken to harvest all the apples at a given rate, we can use this function:
def time_taken(rate):time = 0for i in range(len(apples)):time += (apples[i] + rate - 1) // ratereturn time
This function takes O(n) where n is the number of apples in the orchard to run, as we iterate over each apple in apples.
Brute-Force Solution
Here is the brute-force solution to the problem:
def min_rate(apples, h):def time_taken(rate):time = 0for i in range(len(apples)):time += (apples[i] + rate - 1) // ratereturn timerate = 1while time_taken(rate) > h:rate += 1return rate
Thus, the total time complexity of the brute-force approach is O(n * (max(apples) - 1)), as we iterate from 1 to the maximum number of apples in the orchard. For each iteration, we calculate the time taken to harvest all the apples using the time_taken function in O(n) time.
Binary Search Approach
One way to visualize all the rates we check in the brute-force approach is like this, shown for when apples = [4, 7, 9, 12] and h = 6.
The array on top represents the rate we are trying to harvest apples at, while the array on the bottom represents if that corresponding time is less than or equal to the given time limit h (F for False, T for True). Our brute-force solution returns the rate corresponding to the first T in the bottom array, or 7.
Now let's image our brute-force solution tried everything between 1 and the max_apples in the orchard, instead of returning after the first T. Then the array would look like this:
Why visualize the problem this way? Well, we have a sorted array on top, and a search condition ("find the first T") on the bottom. If we can find a way to eliminate half of the array from our search space at each step, then we can use binary search to solve this problem in O(log(max(apples)) * n) time.
Reducing Search Space
Let's set up the pointers like we do in classic binary search:
At this point, mid points to a rate of 6 apples per hour. This would take 7 hours to harvest all the apples, which is too slow. So we need to reduce our search space.
How should we do it? Well, if 6 apples per hour is already too slow, then anything slower than 6 apples will also be too slow. So we can set left = mid + 1 to discard the left half of the array. Now we're doing binary search!
Next iteration: set mid = (left + right) // 2. Now, mid points to a rate of 9 apples per hour. This would take 5 hours to harvest all the apples, which is fast enough. But can we do better? (i.e. can we find a slower rate that still lets us finish in time?).
We're not sure yet, so let's keep searching. At this point, we can discard the right half of the array by setting right = mid - we know that any rate faster than 9 apples per hour will not be a better answer than 9.
Note how we set right = mid instead of right = mid - 1. This is because mid is still a valid answer, and we don't want to remove it from our search space just yet, like we would if we set it as mid - 1.
This binary search continues until left and right are equal.
- Set mid = (left + right) / 2 = 8 apples per hour.
- This is fast enough (T), so we set right = mid.
- Set mid = (right + left) / 2.
- This is still fast enough (T), so set right = mid.
Now, left = right, our search space only has one element left. We can return the answer as left (or right).
Optimal Solution
class Solution:def minHarvestRate(self, apples, h):# Binary search on harvest rate: find minimum rate to finish in h hoursdef time_taken(rate):time = 0# Calculate total time needed at this harvest ratefor i in range(len(apples)):# Ceiling division: (apples[i] + rate - 1) // ratetime += (apples[i] + rate - 1) // ratereturn time# Binary search bounds: minimum rate = 1, maximum rate = max applesleft, right = 1, max(apples)# Binary search for minimum valid harvest ratewhile left < right:mid = (left + right) // 2if time_taken(mid) > h:# Rate too slow, need faster rateleft = mid + 1else:# Rate is sufficient, try slower rateright = midreturn left
Complexity Analysis
Time Complexity: O(log m * n) where m is the maximum number of apples on a tree and n is the number of trees in the apples array. Our binary search runs O(log m) times, and each time it runs it takes n operations to check how long it takes to collect all the apples for that rate.
Space Complexity: O(1). We are using only a constant amount of space.
Login to track your progress
Your account is free and you can post anonymously if you choose.