# Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y_1, ..., y_M$ ?

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

• What have you tried? What approaches have you considered, and why did you reject them? What algorithmic design paradigms have you tried, and what happened when you tried them? Have you tried solving some special cases?
– D.W.
Mar 14 '16 at 2:45
• I tried brute force and dynamic programming. But the first was certainly to slow and in second approach my algorithm wasn't correct.
– Igor
Mar 14 '16 at 11:02

Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.