Formatted question description: https://leetcode.ca/all/296.html
296 Best Meeting Point A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|. For example, given three people living at (0,0), (0,4), and (2,2): 1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6. Hint: Try to solve it in one dimension first. How can this solution apply to the two dimension case?
First look at the situation where there are two points A and B in one dimension.
It can be found that as long as the meeting is that the location P is in the interval [A, B], no matter where it is, the sum of the distances is the distance between A and B. If P is not between [A, B], then the sum of the distances is Will be greater than the distance between A and B, now add two more points C and D:
The best position of point P is in the interval [A, B], so that the sum of the distances from the four points is the AB distance plus the CD distance.
Just sort the positions, then subtract the first coordinate from the last coordinate, which is the CD distance, and subtract the second coordinate from the penultimate, the second coordinate, which is the AB distance. And so on, until the middle stop.
The one-dimensional situation is analyzed, and the two-dimensional situation is the addition of two one-dimensional results.