Separating numbers with a minimal difference

Question

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?

Answer 1

As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$).

For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.

The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.

To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is an open interval. (Note here we're not concerned with release and due dates of individual tasks.)

This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.

Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)<r$ there is no feasible schedule for the $n$ tasks. Further, if $r\leq B(r,d,n,F)<r+1$ no other task can start in $(B(r,d,n,F)-1,r)$ since otherwise there is again no feasible schedule for the $n$ tasks, and thus $(B(r,d,n,F)-1,r)$ can be declared a forbidden region.

It turns out that this logic is sufficient to find all forbidden regions that are required to make Schrage's heuristic work. Assume that tasks are ordered such that $r_1\leq r_2\leq\cdots\leq r_n$ and write $n(r,d)$ for the number of tasks which are released and due in the closed interval $[r,d]$.

1. set $F=\emptyset$
2. for tasks $i=n,n-1,\ldots,1$:
3.   $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
4.   if $c<r_i$: return "no feasible schedule"
5.   else if $r_i\leq c<r_i+1$: set $F=F\cup\{(c-1,r_i)\}$

A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.

Answer 2

Your problem is known as non-preemptive single-machine scheduling with release times and deadlines, with tasks of identical length, and can be solved efficiently using Schrage's greedy heuristic.

Let us first describe the problem more formally. We are given a sequence of time intervals $[r_i,d_i]$ and a sequence of job lengths $p_i$. We want to schedule each job within its interval, so that no two jobs intersect.

In our case $r_i = a_i$, $d_i = b_i + 2$, and $p_i = 2$. The starting time of each job $c_i$ thus satisfies $a_i \leq c_i \leq b_i$, and two jobs conflict if $(c_i,c_i+2)$ intersects $(c_j,c_j+2)$, which is the same as $|c_i - c_j| < 2$. (Without loss of generality, all jobs are scheduled at integer times.)

Schrage's heuristic is a common heuristic which is optimal in some cases, though not necessarily this one. However, other algorithms exist in the literature which do solve this problem efficiently.

Answer 3

Let A be the smallest of the $a_i$. Then there are two choices for the first $c_i$ to pick that cannot obviously be improved: One, find the i such that $a_i = A$ and $b_i$ is as small as possible, then let $c_i = a_i$. Two, pick j such that $a_j = A+1$, $b_j<b_i$, and $b_j$ as small as possible, then let $c_j=b_j$ (this may not be possible). Then remove that item from the list of intervals, update all $a_i$ to be greater by two than the $c_i$ that was picked, and check that no $b_i$ is too small. Depth first search and backtracking will find a solution.

There is a good chance that this is fast, since the first choice is not bad as a heuristic.

If there are exactly k intervals with $a_i < A$ for some A, and we find k values $c_i <= A-2$ then these $c_i$ are optimal and backtracking for these k items cannot help and will never be needed. On the other hand, if there are too many values $b_i$ too close together, that can be used to prove there is no solution.

Finally, the problem can be approached from the smallest $a_i$, or equally well from the largest $b_i$.