algorithm - 加权间隔移动，寻找最优分布

Question

我正在寻找算法名称(如果它已经存在)或一些解决此问题的提示。

我有一组 N 个作业，每个作业包含间隔，这些间隔可能重叠也可能不重叠。一项特定作业中的所有间隔具有相同的权重、长度和最大类次值。我想要的是通过移动一项工作的所有间隔以最小化峰值来找到最佳(或接近最佳)分布。您只能向前移动间隔(正值)。该算法的输出将是移位间隔的值。

例子:

我们有工作 A、B 和 C。
作业A:长度=2，重量=1，最大位移=0(不能移动)
作业 B:长度=1，重量=3，最大类次=2
作业 C:长度=3.5，重量=5，最大类次=15

如您在第一张图片中所见，存在三个峰值(第一个在 2 和 3 之间，第二个在 4 之前，最后一个峰值在 6 左右)。在第二张图片中进行优化后，您可以看到通过将间隔 B 和 C 移动某个值来移除三个峰中的两个。第二个峰值无法优化，因为作业 C 中的间隔重叠，我们只能一次移动所有间隔。
此示例的输出为:作业 A:0，作业 B:1.5，作业 C:9.5

谢谢。

Answer 1

您可以尝试用于机器托管的共享感知算法:http://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/SindelarSS11.pdf .