空间填充算法？

Question

我现在正在研究一个我找不到名称的问题，所以使用Google搜索什么是不可能的，因此我试着在这里描述它。

想象一下，我们在纸上得到了一个范围或一些主线。现在我们得到了许多随机变长的小行，再加上它们指定了它们开始的范围。我需要选择一组这些较小的线条，因此，我们可以看到主线条的空间将尽可能最小。所以通常我们试图用最小的块来覆盖主线，这些块已经最有效地定义了位置和长度。

除了回答关于如何执行这个任务，我很高兴知道这个问题的名称，因为我确定这是编程时相当常见的，也可以推广到比一个更多的维数..

由于thiton提醒我，妮允许交迭（ofcourse，这将是非常废话otherway）

Answer 1

这看起来像我的动态编程。首先，对时间间隔进行排序，以便您可以按最右边的非递减顺序处理它们。现在我们试着找出每个x的最佳方法来覆盖点< = x。当我们拿起一个以T结尾的新时间间隔时，我们最终将获得点数为< = T的掩护，最好的方法是通过查看我们迄今为止找到最佳解决方案的解决方案来获得点< = S，其中S是最大的S < =我们新区间的左边点。通过将解决方案存储在排序的集合中，比如红色/黑色树，您可以合理快速地找到最佳匹配。

处理完所有间隔后，您可以查看所有最佳解决方案，考虑到其中一些解决方案将在您的生产线结束之前结束，并挑选总体赢家。

Answer 2

这让我想起了一点http://en.wikipedia.org/wiki/Knapsack_problem也许有点帮助的。

Answer 3

解决方案：选择所有线段。你无法做得更好，因为每一点都可能被覆盖。

Answer 4

此问题几乎等于Set Cover problem，一个NP完全问题。它的不同之处在于SCP是用有限集合来表述的。在O（L/e）中，您的版本可以在O（K log K）时间（K =子线数）或未加权的近乎等价的SCP问题中转换为等价的加权SCP问题，反之亦然。时间，因为L =主线长度和准确度e。

维基百科SCP article提到了三种逼近方法：整数线性规划公式，命中集合公式和贪婪算法。

Answer 5

在这个问题中，你有一组线段L1 ... Ln，其中一些重叠。如果两条线段Li和Lj重叠，则当您不能同时在解决方案中设置它们两个时;所以每当两条线段重叠时，就会有排他性约束，只有其中一个线段可以出现在解集中。现在每条线段都有长度，这是线段的“值”，而您的问题等同于要求一组线段具有最大值，但是所有排他性约束均服从，即没有重叠在解决方案中的细分。事实上，原始问题是用欧几里德几何和实数来表述的，并不能改变实际问题是组合和有限性的事实。

它不是KNAPSACK，它也不是设置封面。它看起来像是加权SET PACKING（Wikipedia）的一个实例，但是这里的问题实例是否构成了我不知道的NP完全问题，因为原始问题的几何结构限制了可以生成的约束结构。可能它是，但。

修订

这是每低于@ mcdowella的答案，它不是NP完全问题，但可以被有效解决的问题的一个实例。请参阅下面的评论，了解所有链接和评论。