Algorithm puzzle: minimum cost for allow all persons standing on a line to communicate with each other

Question

I have a algorithm design puzzle that I could not solve.

The puzzle is formulated like this: There are N persons standing on a number line, each of them maybe standing on any integer number on that line. Multiple persons may stand on the same number. For any two persons to be able to communicate with each other, the distance between them should be less than K. The goal is to move them so that each pair of two persons can communicate each other (possibly via other people). In other words, we need to move them so that the distance between any neighboring two persons is smaller than K.

Question: What is the minimum number of total moves? It feels like this falls into greedy algorithm family or dynamic programming. Any hints are appreciated!

Answer 1

We can do the following in O(n):

Calculate the cost of moving all people to the right of person i towards person i at an acceptable distance:

costRight(A[i]) = costRight(A[i+1]) + (A[i+1] - A[i] - k + 1) * count of people to the right

K = 3;  A = { 0,  3, 11, 17, 21}
costRight = {32, 28, 10,  2,  0}

Calculate the cost of moving all people to the left of person i towards person i at an acceptable distance:

costLeft(A[i]) = costLeft(A[i-1]) + (A[i] - A[i-1] - k + 1) * count of people to the left

K = 3;  A = { 0,  3, 11, 17, 21}
costLeft  = { 0,  1, 13, 25, 33}
costRight = {32, 28, 10,  2,  0}

Now that we have cost from both directions we can do this in O(n):

minCost = min(costRight + costLeft) for all A[i]
minCost = min(32 + 0, 28 + 1, 13 + 10, 25 + 2, 33 + 0) = 23

But sometimes that's no enough:

K = 3;  A = { 0,  0,  1,  8,  8}

      carry:     -2  -4       3
costLeft  = { 0,  0,  0, 11, 11}

      carry: -3   5      -2
costRight = { 8,  8,  8,  0,  0}

The optimum is neither 11 nor 8. Test the current best by moving towards the greatest saving:

move 1 to 2, cost = 1

K = 3;  A = { 0,  0,  2,  8,  8}

      carry:     -2  -2     -10
costLeft  = { 0,  0,  0, 10, 10}

      carry: -2          -2
costRight = { 6,  6,  6,  0,  0}

minCost = 1 + min(0 + 6, 0 + 6, 0 + 6, 10 + 0, 10 + 0) = 1 + 6 = 7

Not quite sure how to formularize this efficiently.

Answer 2

Here is a greedy algorithm written in Java, but I don't know if it gives the optimal solution in every case. Also it is more a proof of concept, there is some room for optimizations.

It is based on the fact that two neighbouring persons must not be more than K apart, the next neighbour must not be more than 2K away and so on. In each step we move the person that "violates these constraints most". The details of this calculation are in method calcForce.

package so;

import java.util.Arrays;

public class Main {

    public static void main(String args[]) {
        int[] position = new int[] {0, 0, 5, 11, 17, 23};
        int k = 5;

        solve(position, k);
    }

    private static void solve(int[] position, int k) {
        if (!sorted(position)) {
            throw new IllegalArgumentException("positions must be sorted");
        }
        int[] force = new int[position.length];
        int steps = 0;
        while (calcForce(position, k, force)) {
            int mp = -1;
            int mv = -1;
            for (int i = 0; i < force.length; i++) {
                if (mv < Math.abs(force[i])) {
                    mv = Math.abs(force[i]);
                    mp = i;
                }
            }
            System.out.printf("move %d to the %s%n", mp, force[mp] > 0 ? "right" : "left");
            if (force[mp] > 0) {
                position[mp]++;
            } else {
                position[mp]--;
            }
            steps++;
        }
        System.out.printf("total: %d steps%n", steps);
    }

    private static boolean calcForce(int[] position, int k, int[] force) {
        boolean commProblem = false;
        Arrays.fill(force, 0);
        for (int i = 0; i < position.length - 1; i++) {
            for (int j = i + 1; j < position.length; j++) {
                int f = position[j] - position[i] - (j - i) * k;
                if (f > 0) {
                    force[i] += f;
                    force[j] -= f;
                    commProblem = true;
                }
            }
        }
        return commProblem;
    }

    private static boolean sorted(int[] position) {
        for (int i = 0; i < position.length - 1; i++) {
            if (position[i] > position[i+1]) {
                return false;
            }
        }
        return true;
    }
}