定位有序的间隔序列，以便与另一个固定间隔序列进行最大对齐

Question

我有两个间隔序列。

第一个是固定的，不重叠的，所以类似于：

[1..10], [12..15], [23..56], [72..89], ...

第二个不是固定的，所以它只是间隔长度的有序列表：

[7, 2, 5, 26, ...]

手头的任务是：

• 将第二个列表中的每个间隔放置在给定的起点，以便第二个列表成为一个固定的、不重叠的间隔列表，就像第一个列表一样，同时保持其顺序
• 查找使某个列表中某个间隔内的整数数量最少，但不在另一个列表的任何间隔内的整数数量最少的对齐方式

很简单的例子：

[25..26], [58..68], [74..76], [78..86]

[10, 12]

最佳解决方案是将长度为10的区间放在[58..68]处，将长度为12的区间放在[74..86]处，这将导致数字25、26和77仅在一个列表中，而不在另一个列表中。

我想出的唯一一件似乎有点帮助的事情是，如果我按顺序排列间隔，我知道我已经创建了多少“惩罚”间隔，所以我有分数的上限，这意味着我有一个可接受的启发式，我可以进行A*搜索，而不是查看整个树。然而，数字的总范围从0到大约34M，所以我想要更好的东西。

任何帮助都会很热情！

Answer 1

好的，这里有一个经过深思熟虑的答案。它应该在多项式时间内工作，但是我没有费心检查索引是什么。很可能得到比这里概述的答案更好的索引。细节留给读者练习：-）我希望它不会太不清楚。

我将解决方案的分数定义为出现在两个区间列表中的整数数量。让f（i， m）是仅使用前i个区间长度可能获得的最高分，前提是您的区间都不超过m。对于固定i，函数f本质上是一个（非严格）从整数到整数有界子集的递增函数。因此：

• f（i，m）的所有值，对于m

这意味着可以使用有限的数据结构来表示f（i，m）的所有值（仍然考虑i的固定值）。

现在让F（i）是这个数据结构的值，代表F（i，m）的所有值。我声称，给定F（I），可以计算F（I 1）。要做到这一点，我们只需要为所有x回答以下问题：如果我将新的间隔设置为x，那么我能得到的最佳解决方案有多好？但我们知道这是什么-这只是f（i，x）我们在这段时间内得到的分数。

因此，如果n是第二个列表中的区间数，则最佳解的分数将为F（n）。

要真正找到解决方案，您可以从这一点开始反向工作。

你知道你能得到的最好分数是多少。说它是\u 0。然后将最后一个间隔放在尽可能左的位置，前提是它允许您为s\U 0评分。也就是说，求最小的m，使得f（n，m）=s\u 0；放置间隔，使其仅停留在m的边界内。

然后，让s_1是您需要从所有其他间隔中获得的分数，以便获得s_0。将下一个最后一个间隔尽可能放在最左边，前提是您仍然可以s_1得分。也就是说，找到最小的m，使得f（n， m）=s_1；并将间隔放置在m的界内。

等等