Post Office Problem

On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

Example:

Given array a = [1,2,3,4,5], k = 2.

return 3.

Solution:

In above example, we could easily see that a post office need to be built at 3 when k = 1. This means if there is only one post office, this office should always be built at the center of the sorted array to provide the least sum of all distances.

Therefore, we could pre-calculate all the least sum of all distances for villages from i to j with only one post office. Once we find all the distances, we could use f[n][k] to represent the total distance for array with n length and k post offices. The state function could be defined as:

f[i][l] = Math.min(f[i][l], f[j][l - 1] + dist[j + 1][i]), where j from 0 to i - 1

This formula indicates that we would like to find the minimal split between the range 0 - i. In the second parameter of Math.min, we have cut finding l post office in range 0 - i to two parts:

1. Find l - 1 post office in range 0 - j
2. Find 1 post office in range j - i

Code:

public class Solution {
    /**
     * @param A an integer array
     * @param k an integer
     * @return an integer
     */
    public int postOffice(int[] A, int k) {
        if (A == null || A.length == 0 || k == 0 || k >= A.length) {
            return 0;
        }
        Arrays.sort(A);
        int n = A.length;
        int[][] dist = preCaclulate(A);
        int[][] f = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            f[i][1] = dist[1][i];
        }
        for (int l = 2; l <= k; l++) {
            for (int i = l; i <= n; i++) {
                f[i][l] = Integer.MAX_VALUE;
                for (int j = 0; j < i; j++) {
                    f[i][l] = Math.min(f[i][l], f[j][l - 1] + dist[j + 1][i]);
                }
            }
        }
        return f[n][k];
    }

    private int[][] preCaclulate(int[] A) {
        int n = A.length;
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int mid = (i + j) / 2;
                for (int l = i; l <= j; l++) {
                    dist[i][j] += Math.abs(A[l - 1] - A[mid - 1]);
                }
            }
        }
        return dist;
    }
}