Maximize minimum distance between arrays

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.

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

Lets look at an example with optimal choices, x (horizontal arrays A, B, C, D):

A            x
B    b    x        b
C   x             c
D     d             x

Our recurrence based on range could be: let f(low, excluded) represent the maximum closest distance between two chosen elements (from arrays 1 to n) of the subset without elements in excluded, where low is the lowest chosen element. Then:

(1)

f(low, excluded) when |excluded| = n-1:
  max(low)
    for low in the only permitted array

(2)

f(low, excluded):
  max(
    min(
      a - low,
      f(a, excluded')
    )
  )
  for a ≥ low, a not in excluded'
    where excluded' = excluded ∪ {low's array}

We can limit a. For one thing the maximum we can achieve is

(3)

m = (highest - low) / (n - |excluded| - 1)

which means a need not go higher than low + m.

Secondly, we can store results for all f(a, excluded'), keyed by excluded' (we have 2^10 possible keys), each in a decorated binary tree ordered by a. The decoration will be the highest result achievable in the right subtree, meaning we can find the max for all f(v, excluded'), v ≥ a in logarithmic time.

The latter establishes a dominance relationship and clearly we are intetested in both a larger a and a larger f(a, excluded') so as to maximise the min function in (2). Picking an a in the middle, we can use a binary search. If we have:

a - low < max(v, excluded'), v ≥ a

  where max(v, excluded') is the lookup
  for a in the decorated tree

then we look to the right since max(v, excluded) indicates there's a better answer on the right, where a - low is also larger.

And if we have:

a - low ≥ max(v, excluded), v ≥ a

then we record this candidate and look to the left since to the right, the answer is fixed at max(v, excluded), given that a - low could not decrease.

In order to conduct the binary search on the range, [low, low + m] (see (3)), rather than merge and label all the arrays at the outset, we can keep them separate and compare the closest candidates to mid out of each array we are currently permitted to choose a from. (The trees have the mixed results, keyed by subset.) (The flow of this part is not completely clear to me.)

Worst case with this method, given that n = C is constant seems to be

O(C * array_length * 2^C * C * log(array_length) * log(C * array_length))

C * array_length is the iteration on low
Each low can be paired with 2^C inclusions
C * log(array_length) is the separated binary-search
And log(C * array_length) is the tree lookup

Simplifying:

= O(array_length * log^2(array_length))

although in practice, there could be many dead-end branches that exit early where a full selection wouldn't be possible.

In case, it wasn't clear, the iteration is on a fixed lowest element in the selection. In other words, we want the best f(low, excluded) for all different lows (and excludeds). For bottom-up, we would iterate from the highest value down so our results for a get stored as we iterate.