Algorithm to find the least sum of displacements to make an intersection of all closed intervals non-empty

Question

We are given with an array of $n$ closed intervals on real line. Intervals are given by their ends $[a_i, b_i]$. We may displace any interval by adding some real value $d_j$ to both its ends. All basic arithmetic operations take $O(1)$ operations.

I need to construct an algorithm which makes the intersection of all intervals non-empty in $O (n \operatorname{log} n)$ steps in a such way, that the sum of modules of all displacements $\sum |d_j|$ is minimal.

Since all of our intervals are closed it seems natural for me to make at least one common point. So, for example, we can find an interval with the leftmost right end and save its coordinate as $x$. Then for each of the remaining intervals we compare its left end with $x$. If it's equal to $x$ then we have a common point. If it is less than $x$, we check its right end and move it left if necessary. If the left end of the interval is greater than $x$, move interval right.

I need a hint about how I can prove that algorithm described above is correct. Or the way to see it isn't, since it can be done in $O(n)$. This makes me doubt.

Thanks in advance!

Answer 1

Consider $[0,1], [1001,1002], [1002,1004]$. If I understand your algorithm correctly, you would choose the first interval, as it has the "leftmost right end" meaning the second interval would move $1000$ to the left and the third $1001$ to the left. This would cost $2001$.

Instead, our algorithm should displace $[0,1]$ to the right $1001$ to give a total cost of $1001$.

Answer 2

I think making one point common if such a point doesn’t already exists would be enough and also that the minimum can be achieved at the starts or ends of each range. So you will have to check which point gives the minimum and make your shifts accordingly after you get the optimal situation. I think this can be implemented in $n log(n)$ time. Suppose you want to make the common point at $x_*$ you want the sum of end points of ranges which end before $x_*$ and the sum of starts of ranges which begin after $x_*$, these can be precomputed after sorting the end points array and start point arrays. Thus to check the minimum number of shifts for a choosen x will be constant time. Now you will have to check for each end and start point as those will be the possible x’s. Thus total time N and you’ll need $nlog(n)$ for precomputing.