Maximize minimum distance between arrays

Question

Lets say that you are given n sorted arrays of numbers and you need to pick one number from each array such that the minimum distance between the n chosen elements is maximized.

Example:

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10 and every array could have ~10^3-10^4 elements.

In this example the optimal solution to maximize minimum distance is pick numbers: 500, 350, 200 or 0, 200, 350 where min distance is 150 and is the maximum possible of every combination.

I am looking for an algorithm to solve this. I know that I could binary search the max min distance but I can't see how to decide is there is a solution with max min distance of at least d, in order for the binary search to work. I am thinking maybe dynamic programming could help but haven't managed to find a solution with dp.

Of course generating all combination with n elements is not efficient. I have already tried backtracking but it is slow since it tries every combination.

Answer 1

I am going to give an algorithm that for a given distance d, will output whether it is possible to make a selection where the distance between any pair of chosen numbers is at least d. Then, you can binary-search the maximum d for which the algorithm outputs "YES", in order to find the answer to your problem.

Assume the minimum distance d be given. Here is the algorithm:

for every permutation p of size n do:
    last := -infinity
    ok := true
    
    for p_i in p do:
        x := take the smallest element greater than or equal to last+d in the p_i^th array (can be done efficiently with binary search).
        if no such x was found; then
            ok = false
            break
        end

        last = x
    done

    if ok; then
        return "YES"
    end
done

return "NO"

So, we brute-force the order of arrays. Then, for every possible order, we use a greedy method to choose elements from each array, following the order. For example, take the example you gave:

arrays:
[0, 500]
[100, 350]
[200]

and assume d = 150. For the permutation 1 3 2, we first take 0 from the 1st array, then we find the smallest element in the 3rd array that is greater than or equal to 0+150 (it is 200), then we find the smallest element in the 2nd array which is greater than or equal to 200+150 (it is 350). Since we could find an element from every array, the algorithm outputs "YES". But for d = 200 for instance, the algorithm would output "NO" because none of the possible orderings would result in a successful selection.

The complexity for the above algorithm is O(n! * n * log(m)) where m is the maximum number of elements in an array. I believe it would be sufficient, since n is very small. (For m = 10^4, 10! * 10 * 13 ~ 5*10^8. It can be computed under a second on a modern CPU.)

Answer 2

n ≤ 10 suggests that we can take an exponential dependence on n. Here's an O(2ⁿ m n)-time algorithm where m is the total size of the arrays.

The dynamic programming approach I have in mind is, for each subset of arrays, calculate all of the pairs (maximum number, minimum distance) on the efficient frontier, where we have to choose one number from each of the arrays in the subset. By efficient frontier I mean that if we have two pairs (a, b) ≠ (c, d) with a ≤ c and b ≥ d, then (c, d) is not on the efficient frontier. We'll want to keep these frontiers sorted for fast merges.

The base case with the empty subset is easy: there's one pair, (minimum distance = ∞, maximum number = −∞).

For every nonempty subset of arrays in some order that extends the inclusion order, we compute a frontier for each array in the subset, representing the subset of solutions where that array contributes the maximum number. Then we merge these frontiers. (Naively this costs us another factor of log n, which maybe isn't worth the hassle to avoid given that n ≤ 10, but we can avoid it by merging the arrays once at the beginning to enable future merges to use bucketing.)

To construct a new frontier from a subset of arrays and another array also involves a merge. We initialize an iterator at the start of the frontier (i.e., least maximum number) and an iterator at the start of the array (i.e., least number). While neither iterator is past the end,

1. Emit a candidate pair (min(minimum distance, array number − maximum number), array number).
2. If the min was less than or equal to minimum distance, increment the frontier iterator. If the min was less than or equal to array number − maximum number, increment the array iterator.

Cull the candidate pairs to leave only the efficient frontier. There is an elegant way to do this in code that is more trouble to explain.