Minimum number of intervals to cover all possible colors

Question

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some of $n$ points such that from each color, $c_i$ ($1 \leq i \leq 3$), there is at least one point in one of chosen intervals.

I assume if the number of colors was a parameter of the problem (like $n$), it could be proved that it is in NP. Then by reducing Set Cover to the above problem, it would actually become an NP-Complete problem too. But I hope by setting a restriction on number of colors (here number of colors is restricted to $3$) the problem can be solved in polynomial time, yet I have not found any polynomial solutions.

Answer 1

The trivial solution concluded from the comments is as follows.
Order (~$O(n\log{n})$) the given points as $P=[p_1,...,p_n]$, such that $$i < j \iff p_i < p_j$$. By iterating from $p_1$ to $p_n$ in $O(n^2)$ find all possible intervals of length 1 store them as a tuple of $(\text{subarray of points they contain}, \#\text{unique colors they contain})$.
As the minimum number of intervals can be either.

• 1: one interval with $\#\text{unique colors they contain}=3$,
• 2: two intervals one with $\#\text{unique colors they contain}=2$ and one with $\#\text{unique colors they contain}=1$ (with no common color between two intervals),
• 3: three intervals each with $\#\text{unique colors they contain}=1$ with (no common color).

Check cases 1, 2, and 3 (each in $O(n^2)$) one after another. in worst case the problem can be solved with 3 intervals and in $O(n^2)$.