获取最大子集，其元素之间的差值满足指定的最小距离要求。

Question

我有一个整数集合，例如：{1,3,4,5,10}，现在我想要最大的子集（最大=元素最多），其中每个元素之间的最小距离/差异是一定的。

例如，对于集合{1,3,4,5,10}和最小距离2，结果可能是：

{1,3,5,10}

或对于距离3：

{1,5,10}

是否存在（良好/高效）的算法来解决这个问题？

- Nick Russler

---

你的意思是说“距离”指的是“差异”吗？ - Luchian Grigore

这很容易转化为独立集问题。不幸的是，它是NP完全问题，所以这并不能让你走得更远... - tskuzzy

可能是日期集合的子集，最大化且具有一定距离的重复内容。 - Saeed Amiri

我复制了这条消息，因为有人告诉我用整数而不是日期重新提出问题。旧帖子可以删除。 - Nick Russler

@NickRussler，我的解决方案中整数和日期没有区别，事实上在大多数语言中日期基本上只是一个 int64，所有的算法都不会改变，你可以轻松找到它。 - Saeed Amiri

Answer 1

这绝对不是一个 NP 完全问题。

实际上，它是经典的 区间调度问题的一种特殊情况，在正常的区间调度问题中，长度是不固定的。

在您的问题中，您可以将每个数字视为一个区间的开始时间，并且每个区间都有您的 "最小距离" 作为区间长度。

每个区间都有一个完成时间，即开始时间 + 区间长度

因此，解决方案如下：

1 按完成时间对所有区间进行排序。

2 按排序顺序逐个遍历它们，将与结果集中所有现有区间兼容的区间添加到结果集中。

这个解决方案是最优的，并具有 O(nlogn) 的时间复杂度。

您可以在上面的链接中找到关于贪心算法的证明和信息。

- xvatar

Answer 2

是的，以下贪心算法提供最佳解决方案。按排序顺序扫描整数，如果先前选取的整数足够远，则取每个整数。正确性通过归纳证明得出，对于每个解决方案S和每个整数u，贪心解决方案选择至少与S相同数量的整数≤u。

- just keep walking

Answer 3

大致如下：

1）对输入进行排序。

2）遍历输入并标记每个元素，标记为如果选择该元素，则会从集合中排除多少个元素。

3）按顺序从可用元素中选择标记最低的元素。

4）删除被排除的元素。

5）重复步骤3和4。

因此，在您的示例中：

1  3  4  5  10     - difference 3

第一步已经完成，进入第二步我们得到：

1  3  4  5  10
1  3  2  2  0

解释 - 如果我们选择1，我们将排除数字-3；如果我们选择3，我们将排除数字-1、4和5，以此类推...

下一步:

• 选择10，不删除任何内容。- 1 3 4 5 (10)
• 选择1，删除3。- (1) 4 5 (10)
• 选择4（或5），删除5（或4）- 1 4 10

我不能保证这会起作用，但这是一个开始...

- Luchian Grigore