Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time?
My attempt is the following greedy strategy: Sort the intervals by the smaller left endpoint, breaking ties by the smaller right endpoint. Then, as long as possible, choose the leftmost feasible number from each interval.
However, this doesn't work: the first interval may be $[5,9]$ and the second interval $[6,6]$. Choosing $5$ from the first interval rules out choosing anything from the second interval. It would be better to choose $6$ from the second interval and $8$ from the first interval.
[(1, 3), (2, 3)]as that will greedily choose
(2, 3)and then nothing can be chosen for
(1, 3). $\endgroup$