First of all we need to sort all the given stall positions. Then we can do a very good trick, we can try finding the solution from the solution set. Take the maximum and minimum number which can be the answer. We can write a function which checks if the current number satisfies the task requirements in O(n) time. Then we can take the maximum and minimum possible answer, and with binary search get to the final answer. Check for the middle, if the middle answer is OK then we can check the middle of that middle and the maximum value. And so on, until we are down to 2 or 1 answers which we can check manually.
No comments:
Post a Comment