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 usingManhattan 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.

​

這道題讓我們求最佳的開會地點，該地點需要到每個為1的點的曼哈頓距離之和最小，題目中給了我們提示，讓我們先從一維的情況來分析，那麼我們先看一維時有兩個點A和B的情況,

______A_____P_______B_______

那麼我們可以發現，隻要開會為位置P在 [A, B] 區間内，不管在哪，距離之和都是A和B之間的距離，如果P不在 [A, B] 之間，那麼距離之和就會大于A和B之間的距離，那麼我們現在再加兩個點C和D：

______C_____A_____P_______B______D______

我們通過分析可以得出，P點的最佳位置就是在 [A, B] 區間内，這樣和四個點的距離之和為AB距離加上 CD 距離，在其他任意一點的距離都會大于這個距離，那麼分析出來了上述規律，這題就變得很容易了，我們隻要給位置排好序，然後用最後一個坐标減去第一個坐标，即 CD 距離，倒數第二個坐标減去第二個坐标，即 AB 距離，以此類推，直到最中間停止，那麼一維的情況分析出來了，二維的情況就是兩個一維相加即可.

public class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> xPoints = new ArrayList<>();
        List<Integer> yPoints = new ArrayList<>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    xPoints.add(i);
                    yPoints.add(j);
                }
            }
        }

        return getMP(xPoints) + getMP(yPoints);
    }

    private int getMP(List<Integer> points) {
        Collections.sort(points);
        int i = 0, j = points.size() - 1;
        int res = 0;
        while (i < j) {
            res += points.get(j--) - points.get(i++);
        }
        return res;
    }
}