there are n players. they have to collect m points.all the players and coins are in 1 D space ie on a number line.The initial location of all the players is given as the array players and locations of all points is given in points array.in one second a player can either move 1 step left or 1 step right or not move at all.A point is considered collected if any of the n players had visited the point;s location . the players can move simultaneously and independently of each other every second. the task is to find the minimum time in seconds required to collect all the points if players act optimally.
Example:
n=3, players = [3,6,7]
m = 4 points = [2,4,7,9] Ans = 2 seconds.
my approach = binary search on time and check if it possible to reach all points in time t using two points by checking if absolute distance between the player and point is less than equal to max allowed by time t. but this gives false positive if the players is moving left and then has to come back to a point on its right in same time t.
how to solve this??
Auto comment: topic has been updated by tanishq2507 (previous revision, new revision, compare).
Binary Search works in my mind
The most-left player should collect the most-left point if he can and if it still have time he should collect as many points to the right as possible, the next player should repeat the same process collecting first the most-left point that the previous player didn't collect if he can.
It may be optimal for the leftmost player (and all others as well) to collect some points to the right before going left (for example, if there is a point 1 step to the right and a point 1000 steps to the left). It's not that difficult to modify your approach to accommodate for this, though (just always pick the option that goes further right).
Oh yeah this makes sense