Simple algorithm to select separated points in closed intervals

Question

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\ \Delta = \min_{1 \leq i \leq j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ can always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

Answer 1

First note that in any optimal solution we can always have $x_1 = a_1$ as we wish to maximize distances, and $x_1 = a_1$ unconditionally does that without sacrificing distance anywhere.

Secondly note that while our 'smallest differences' metric we want to optimize appears a global problem, it really is not if we also sort our $x$. We can have the equivalent definition:

$$\Delta = \min_{1 \leq i < K} \left( x_{i+1} - x_i \right)$$

Now suppose our candidate solution has value $\Delta$. Then given $x_i$ we can find the leftmost $x_{i+1}$:

$$x_{i+1} = \min_y \{ y \mid y \in S \wedge y \geq x_i + \Delta\} $$

So we find $x_1, x_2, \dots$ until we are done. Repeatedly finding which interval in $S$ (if any) will contain $x_{i+1}$ can be done in a combined $O(K)$ time during this process if you just keep track of the highest used interval so far. If there is no valid interval for $x_{i+1}$, it means $\Delta$ is not a valid outcome, but if we find al values up until $x_K$ it is.

So now we have a $O(K + N)$ time test to see whether a certain $\Delta$ is valid. But we can say with certainty that $\Delta \in [0, b_K - a_1]$. So we can do a binary search on this interval using our test to find a range which contains our optimal $\Delta$.

Since each step in this binary search halves the size of the interval that contains the optimal result, we can find optimal $\Delta$ (and corresponding $x_i$) up to a precision of $2^{-p}(b_K - a_1)$ in $O(p(K+ N))$ time.

If you're a bit smarter you can terminate early and exactly as an optimal solution will always contain a limiting sequence of steps of the minimum distance $\Delta$ starting at the left part of an interval and ending at the right part of an interval. Thus we have $a_i + k\cdot \Delta = b_j$. In other words, if our remaining interval contains only a single value of the form $\frac{b_j - a_i}{k}$ for some $i \leq j$ and $k$, then that is the optimal value and you can terminate the search.