Given is a positive integer integer $ n$ , and integers $ a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $ i$ . What is the complexity of deciding whether there exist integers $ c_1,\dots,c_n$ such that $ a_i\leq c_i\leq b_i$ for all $ i$ and $ |c_i-c_j|\geq 2$ for all $ i,j$ ?
What can be observed is that a greedy algorithm, wherein we assume that $ a_1\leq\dots\leq a_n$ and choose $ c_i$ according to this order, does not necessarily work. For example, we may have $ a_1=1, b_1=4, a_2=b_2=2$ . Putting $ c_1=1$ does not work (it leaves no room for $ c_2$ ), but what works is putting $ c_1=4$ and $ c_2=2$ . Is the problem perhaps NP-hard?