We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The first step is identifying that this problem can be solved with search. Given that it's under the search category let's jump straight to the assumption that a search approach will be the best.
When we're performing a search we need to start by defining some bounds (we need to search between two bounds otherwise how do we know where to start/stop)
How do we define our bounds then? Well let's start with the upper bound.
How many days would it take if ALL machines were equally as slow as the slowest machine?
If the slowest machine takes 5 days, we have 3 machines in total, and our goal is 30 then the worst case scenario is tha ALL machines take 5 days.
Given we have 3 machines that means that after 5 days we'll have 3 items produced. That means the worst case is goal / machines * slowestMachine = 50 days.
We can do the same thing to find the lower bound. Let's assume that all 3 machines are as fast as the fastest machine. Our lower bound is then goal / machines * fastestMachine = 10 days.
Now that we have our lower and upper bounds (10 - 50) we can finally start to search.
With binary search we always start at the middle of our bounds. The middle of our bounds is 35 ((lowerBound + upperBound) / 2) so let's start there.
Next we'll try to calculate how many items would be produced after this many days.
For each machine, how many items does it produce after 35 days? For that we use days / machine. Sum each of these values for each machineto get the total number of items produced by all machines after 35 days.
Now we check if we've met our goal or not. If we produce more than our goal, then the half way point that we chose is too high. If we produced less then the half way point was too low.
All we have to do now is repeat the steps but adjust our upper and lower bounds to be (lowerBound - middlePoint) or (middlePoint - upperBound) depending what side of the line we fell.
Minimum Time Required
You are viewing a single comment's thread. Return to all comments →
The first step is identifying that this problem can be solved with search. Given that it's under the search category let's jump straight to the assumption that a search approach will be the best.
When we're performing a search we need to start by defining some bounds (we need to search between two bounds otherwise how do we know where to start/stop)
How do we define our bounds then? Well let's start with the upper bound.
How many days would it take if ALL machines were equally as slow as the slowest machine?
If the slowest machine takes 5 days, we have 3 machines in total, and our goal is 30 then the worst case scenario is tha ALL machines take 5 days.
Given we have 3 machines that means that after 5 days we'll have 3 items produced. That means the worst case is goal / machines * slowestMachine = 50 days.
We can do the same thing to find the lower bound. Let's assume that all 3 machines are as fast as the fastest machine. Our lower bound is then goal / machines * fastestMachine = 10 days.
Now that we have our lower and upper bounds (10 - 50) we can finally start to search.
With binary search we always start at the middle of our bounds. The middle of our bounds is 35 ((lowerBound + upperBound) / 2) so let's start there.
Next we'll try to calculate how many items would be produced after this many days.
For each machine, how many items does it produce after 35 days? For that we use days / machine. Sum each of these values for each machineto get the total number of items produced by all machines after 35 days.
Now we check if we've met our goal or not. If we produce more than our goal, then the half way point that we chose is too high. If we produced less then the half way point was too low.
All we have to do now is repeat the steps but adjust our upper and lower bounds to be (lowerBound - middlePoint) or (middlePoint - upperBound) depending what side of the line we fell.