Positioning items to maximize separation
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.