Algorithm/DS Problem#9: Assign Golf balls to holes

Given a set of golf balls at n number of coordinates/positions and equal number of holes, each golf ball move takes one minute from one hole to the right or left. What is the minimum time for all the golf balls to go to all holes?

N holes in a straight line

golfballs = [4,-4,2]

holes = [4,0,5]

Solution

Main idea is to minimize the total time it takes for all golf balls to reach holes. The answer depends on the maximum distance that any golf ball has to travel and we have to minimize that distance as much as possible. That’s the greedy strategy is to put every ball to the nearest hole as much as possible.

(1) Sort the golfballs and holes arrays
-4 , 4, 2 (sorted)
0, 4 ,5 (sorted)

(2) Put -4 to 0th hole 2nd ball to 4th hole etc

(3) Can you think about any edge cases?