7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What if you add "most restricted first"? $\endgroup$
    – greybeard
    Commented Nov 7, 2022 at 5:20
  • $\begingroup$ Can the intervals overlap ? Can they have common endpoints ? $\endgroup$
    – user16034
    Commented Nov 7, 2022 at 12:38
  • $\begingroup$ His example in the comment contains intervals with the same endpoints $\endgroup$
    – Russel
    Commented Nov 7, 2022 at 13:10
  • $\begingroup$ @YvesDaoust Yes, intervals can overlap, and they can have common endpoints. $\endgroup$
    – simmons
    Commented Nov 7, 2022 at 13:17
  • $\begingroup$ @greybeard That won't work for [(1, 3), (2, 3)] as that will greedily choose 2 from (2, 3) and then nothing can be chosen for (1, 3). $\endgroup$
    – Tyilo
    Commented Nov 9, 2022 at 18:53

2 Answers 2

3
+25
$\begingroup$

This problem can be regarded as a scheduling problem.

Each interval corresponds to a job. For each interval $[L_i,R_i]$, Let $r_i = L_i$ be the release time, $d_i = R_i + 2$ be the deadline, and $p_i = 2$ be the job length. Then, single-machine no-preemption scheduling corresponds to a solution. Scheduling with non-integer start times can be converted to integer start times by taking the floor function, and the schedule remains feasible.

This problem has an $O(n \log n)$-time solution [1].

  • [1] Garey, Michael R., et al. "Scheduling unit–time tasks with arbitrary release times and deadlines." SIAM Journal on Computing (1981).
$\endgroup$
1
  • $\begingroup$ @simmons See: Chrobak, Marek, et al. "A Note on Scheduling Equal-Length Jobs to Maximize Throughput" arxiv.org/abs/cs/0410046 . $\endgroup$
    – pcpthm
    Commented Dec 5, 2022 at 18:53
1
$\begingroup$

I had an idea for a polynomial time algorithm, but here is a counter-example. I leave it visible for the sake of having an interesting input instance. I thought that the decisions didn't propagate too far, but that's clearly not true.

$I = \{ [1,8], [2,3], [3,5], [5,6] \}$. The solution is $\{2,4,6,8\}$.

Invalid solution

 1  2  3  4  5  6  7  8
[·                     ]
   [   ·]
      [      ·]
            [    ]

Valid solution

 1  2  3  4  5  6  7  8
[                     ·]
   [·   ]
      [   ·   ]
            [   ·]

I'm reminded of Hall's theorem here. You could say that for it to be a yes instance, every subset of intervals $S$ need to have $\text{span}(S) \geq 2|S| - 1$, and the intervals $S = \{ [2,3], [3,5], [5,6] \}$ have span $4 < 2\cdot 3 - 1 = 5$.

$\endgroup$
1
  • $\begingroup$ Hall's theorem is listed as Theorem 2.7 in the section, "Polynomial time algorithms for the equal-processing-times case" of Scheduling with release times and deadlines by Jan Elffers, 2014. $\endgroup$
    – John L.
    Commented Nov 26, 2022 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.