The algorithm for shifting the intervals of overlap until there is no overlap

Question

I have a sorted list of overlapping intervals, the intervals are never contained in each other, like

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

The limitation for output is to keep each element as close as possible to its origin (middle of the interval), keep the input order and remove all overlaps. Only an approximate solution is needed. Expected result for entering an example:

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

I only know about the solutions that arise in some style simulators: shifting each element by a certain value in the free direction and iterating until all overlaps are removed.

Is there an existing algorithm to solve this problem?

Answer 1

find the average value:

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 combine them

 4.667 ~ 5 18.667 ~ 19 

start with mines by creating partitions with intervals

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

Note:

this method will not match the original elements as much as possible, but will keep them as close to the original as possible, given their relative values ​​(keeping the center)

EDIT:

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

our input problems:

a ₁ = (a _1,1 , a _1,2 ), ..., a <sub>nsub> = (a <sub> n, 1sub>, and _{n, 2sub>)}

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 // set the intervals

we need to find "d", for example:

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 calculate the derivative to find the min / max OR iterations over d to get the result. in our case, you will need to iterate from 3 to 7

which should do the trick

Answer 2

Given that the solution should be kept in order, we can formulate this problem as a linear program. Let [a _i , b _i ] be the ith interval. Let the variables x _i be the left shift of the i-th interval, and let y _i be the right shift of the i-th interval.

minimize the amount _i (x _i + y _i )
taking into account (*) 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

Replace the constraint (*) by introducing the 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 boils down to calculating the minimum cost that can be done in a lot of time. However, I have a feeling that there is a more direct solution to this problem.

The graph looks something like this:

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