2
$\begingroup$

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \le r_i$. My problem is: given a specific item s, how do I compute the maximum gap possible to the right of s? By maximum gap to the right of s I mean the distance between s and the next item to its right.

Mathematical Description:

More formally, given $s \in [n]$, and $(l_i,r_i)$ for $i\in[n]$ I want to find $$f(s) = \max_{p_1,\dots,p_n} p_t - p_s$$ subject to \begin{align*} 1)\,& l_i \le p_i \le r_i\, \forall\,i \in [n] \\ 2)\,& \forall\,i\ne s,t, \text{ either } p_i \le p_s \text{ or }p_i \ge p_t \text{ (there is no item between s and t)} \end{align*}

In the absence of the second constraint the problem would have been a linear program. The second constraint makes it difficult.

I know how to model this question as an integer program (see https://bit.ly/2Jhf7kJ), but I am interested in an actual algorithm.

$\endgroup$
2
$\begingroup$

Given a specific item $s$, how do I compute the maximum gap possible to the right of $s$? By maximum gap to the right of $s$ I mean the distance between $s$ and the next item to its right.

This is much more useful than the mathematical description.

First note that items that are to the left of $s$ don't hurt us in any way, so if it is possible to put an item to the left of $s$, do so. Then we note that if an item can't go to the left of $s$ we want it as far to the right as possible.

The conclusion? Each item is always at either its left or right boundary, with the exception of $s$. And once you know the position of $s$ you'll also know all the other positions.

So just loop over each interesting position of $s$, discard all items that can go on the left, and then choose the closest item on the right. Out of these closest items, which ever is the furthest is your answer (or well, it's associated position of $s$).

Now what are the interesting positions of $s$? Well it's each time you can put another item to the left of $s$. So it's all the left boundaries (plus one epsilon) of items that fall within $[l_s, r_s]$, and $l_s$ itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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