I’m wondering if a centroid based solution should work for this problem.

It seems that the shortest distance to travel for N people to meet will be a centroid based on their coordinates.

So the centroid coordinates will be:

cx = (x1 + x2 + … + xN) / N

cy = (y1 + y2 + … + yN) / N

And then (because of a rounding error) one would just need to examine the rectangle of size 9 (points around centroid) to check the sums of distance from each of the 9 points to each person coordinate.

If this is a correct approach it will reduce the time complexity to O(n + 9*n) which is O(n)

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5679846214598656

Lesson: https://www.educative.io/collection/page/5642554087309312/5679846214598656/120001