移动重叠间隔直到没有重叠的算法

Question

我有一个重叠间隔的排序列表，间隔从不包含在彼此中，例如，

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

输出的约束是让每个元素尽可能接近它的原点(间隔的中间)，保留输入的顺序，并删除所有重叠。只有一个近似解是必要的。示例输入的预期结果为:

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

我只知道在某些模拟中解决这个问题的解决方案样式:将每个元素沿自由方向移动某个值，然后迭代直到所有重叠都被删除。

是否有现成的算法来解决这个问题？

Answer 1

求总体平均值:

在我们的例子中:

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

求总长度:

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

找到新的最小值/最大值；

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

你可以将它们四舍五入

4.667 ~ 5
18.667 ~ 19

从最小值开始，按间隔创建部分

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

注意:

该方法不会使元素尽可能与原件相等，而是考虑到它们的相对值(保留中心)，使其尽可能接近原件

编辑:

如果你想让所有区间的平均值尽可能接近原始值，你可以实现一个数学解决方案。

我们问题的输入是:

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

我们将定义:

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

我们需要找到一个“d”，例如:

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

min(s)就是我们想要的

在我们的例子中:

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)

现在计算导数以找到最小值/最大值或迭代 d 以获得结果。在我们的例子中，您需要从 3 迭代到 7

应该可以解决问题