Algorithm to shift overlapping intervals until no overlap is left

Question

I have a sorted list of overlapping intervals, intervals are never contained in each other, e.g.,

[(7, 11), (9, 14), (12,  17)]

The constraint for the output is to keep every element as close as possible to its origin (the middle of the interval), preserve the order of the input, and remove all overlap. Only an approximate solution is necessary. The expected result for the example input would be:

[(5,9), (9, 14), (14, 19)]

I'm only aware of solutions that go about this in some simulation style: shift each element by some value in a free direction and iterate until all overlap has been removed.

Is there an existing algorithm to solve this?

Answer 1

find the overall average:

in our example:

(7 + 11 + 9 + 14 + 12 + 17)/6 = 11.667

find the total length:

(11-7) + (14-9) + (17-12) = 4 + 5 + 5 = 14;

find the new min/max;

14/2 = 7
11.667 - 7 = 4.667
11.667 + 7 = 18.667

you can round 'em

4.667 ~ 5
18.667 ~ 19

start from the min, creating the sections by the intervals

(5, (11-7)+5) = (5,9)
(9, (14-9)+9) = (9,14)
(14, (17-12)+14) = (14,19)

NOTE:

this method will not keep the elements as equal as possible to the originals, but will keep them as close as possible to the original considering their relative values (preserving the center)

EDIT:

if you want to keep the averages of all intervals as close as possible to the original, you can implement a mathematical solution.

our problem's input is:

a₁=(a_1,1, a_1,2) , ... , a_n=(a_n,1,a_n,2)

we will define:

ai₁ = a_1,2-a_1,1 // define the intervals

b₁ = (d, d+ai₁)

b_n = (d + sum(ai₁..ai_n-1), d + sum(ai₁..ai_n) )

bi₁ = b_1,2-b_1,1 // define the intervals

we need to find a 'd' such as:

s = sum( abs((a_1,1+a_1,2)/2 - (b_1,1+b_1,2)/2) )

min(s) is what we want

in our example:

a₁ = (7,11), ai₁ = 4, A_avg1 = 9

a₂ = (9,14), ai₂ = 5, A_avg2 = 11.5

a₃ = (12,7), ai₃ = 5, A_avg3 = 14.5

b₁ = (d, d+4) B_avg1 = d+2

b₂ = (d+4, d+9) B_avg2 = d+6.5

b₃ = (d+9, d+14) B_avg3 = d+11.5

s = abs(9-(d+2)) + abs(11.5-(d+6.5)) + abs(14.5-(d+11.5)) = abs(7-d) + abs(5-d) + abs(3-d)

now calculcate the derivative to find min/max OR iterate over d to get a result. in our case you will need to iterate from 3 to 7

that should do the trick

Answer 2

Given that the solution must be order-preserving, we can formulate this problem as a linear program. Let [a_i, b_i] be the ith interval. Let variables x_i be the left shift of the ith interval and y_i be the right shift of the ith interval.

minimize sum_i (x_i + y_i)
subject to
(*) for all i: b_i - x_i + y_i ≤ a_i+1 - x_i+1 + y_i+1
for all i: x_i, y_i ≥ 0

Rewrite constraint (*) by introducing a variable z_i.

for all i: x_i - y_i - x_i+1 + y_i+1 - z_i = 0
for all i: z_i ≥ b_i - a_i+1

Now the problem is reduced to computing a minimum-cost circulation, which can be done in poly-time. I have a feeling, however, that there's a more direct solution to this problem.

The graph looks something like

        (*)
    ---- | ----
   /    z|     \
  /     i|      \
 /   xi  |  xi+1 \
|/ <---- v <---- \|
...     (*)     ...
   ---->   ---->
    yi     yi+1