# Covering all colors with unit intervals

Suppose we are given $$n$$ points on the real line, where each point is colored with a color from set $$C=\{c_1,c_2,\ldots,c_k\}$$ that contains $$k$$ distinct colors. We try to cover the $$k$$ distinct colors with as few unit length intervals as possible.

I think this problem is NP-hard and we can reduce from set cover problem. But I get stuck.

Also when $$k=3$$, is there a polynomial solution. I read this link but I can't understand his idea?

If $$k$$ is part of the input then the problem is NP-hard and you can indeed reduce from the set-cover problem. Let $$x_{1}, \dots, x_k$$ be the items and $$S_1, \dots, S_m$$ be the sets. Create a color for each item. Then, for each set $$S_i$$, create $$|S_i|$$ points on the real line at coordinates $$2i + \frac{1}{|S_i|}, 2i + \frac{2}{|S_i|}, \dots, 2i + 1$$. Color the $$j$$-th of such points with the color of the $$j$$-th item in $$S_i$$. Notice that: (i) one interval cannot cover two points from two sets, and (ii) all points from the same set can be covered with a single interval.
If $$k$$ is not part of the input then the problem is not NP-hard, unless P=NP. Indeed a trivial algorithm guesses one covered point for each color (there are only $$O(n^k)$$ guesses) and then covers the guessed points with the minimum number of intervals (this can be done via an easy greedy algorithm).