How to approach this question?

Revision en2, by tanishq2507, 2024-08-21 21:08:56

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??

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English tanishq2507 2024-08-21 21:08:56 9 Tiny change: 'n\nm = 4 players  = [2,4,' -> 'n\nm = 4 points  = [2,4,'
en1 English tanishq2507 2024-08-21 21:08:19 1090 Initial revision (published)