I've come across this problem, I know that I'm going to binary search the answer (Given the fact that if x(time) is good, x + 1 is also good), but I am very stuck at how to determine if that time is good or not in the first place. Any help would be much appreciated. Thanks in advance,
Note that binary search allows you to change the varying factor.
The original problem requires you to find the minimal
T
given a fixedm
,which is difficult as you don't know how many balloons to assign for each assistant.
Binary search is essentially choosing a fixed
T
and finding the maximalm
every time,which is much simpler since the amount of balloons every assistant can inflate in a given time is easy to find.
The way it works is just like what you have mentioned: if they can make
m
balloons inT
minutes, then they must be able to do it inT+1
minutes.So keep in mind that binary search is transforming one hard problem into
log(n)
simple problems.