算法转移重叠的区间，直到没有重叠留 [英] Algorithm to shift overlapping intervals until no overlap is left

问题描述

我有重叠区间的排序列表，间隔永远不会包含在对方，例如，

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

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

有输出的约束是保持每个元素尽可能接近到它的 原点（区间的中间），preserve输入的顺序，并删​​除所有的重叠。只有一个 近似​​解是必要的。对于本例输入预期的结果将是：

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?

推荐答案

找到整体平均：

在我们的例子：

(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

您可以圆'时间

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)

请注意：

这个方法不会保持元素尽可能平等的原件，但将让他们尽可能接近原来的考虑其相对值（preserving中心）

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)

编辑：

如果你想保持尽可能接近原来的所有间隔的平均值，可以实现数学的解决方案。

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

我们的问题的输入为：

在<子> 1 =（A <子> 1.1 ，一个<子> 1,2 ），...，A <子> N =（A <子> N，1 ，一个<子> N，2 ）

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

我们将定义：

AI <子> 1 = A <子> 1,2 -a <子> 1.1 //定义的时间间隔

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

B ₁ =（D，D + AI <子> 1 ）

b₁ = (d, d+ai₁)

B <子> N =（D + SUM（AI <子> 1 .. AI <子> N-1 ），D +和（AI <子> 1 .. AI <子> N ））

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

双向<子> 1 = B <子> 1,2 -b <子> 1.1 //定义的时间间隔

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

我们需要找到一个D，如：

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））

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

分（s）是我们想要的。

min(s) is what we want

在我们的例子：

在<子> 1 =（7,11），AI <子> 1 = 4，A <子> AVG1 = 9

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

在 ₂ =（9,14），AI ₂ = 5，A <子> AVG2 = 11.5

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

在<子> 3 =（12,7），AI <子> 3 = 5，A <子> avg3 = 14.5

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

B ₁ =（D，D + 4）乙<子> AVG1 = D + 2

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

B ₂ =（D + 4，D + 9）乙<子> AVG2 = D + 6.5

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

B ₃ =（D + 9，D + 14）乙<子> avg3 = D + 11.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）

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)

现在calculcate衍生找到最小/最大或遍历d，来得到一个结果。在我们的例子中，你将需要遍历从3到7

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

这是应该做的伎俩

这篇关于算法转移重叠的区间，直到没有重叠留的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！