algorithm - 获得具有特定最小距离/差异的最大整数子集

Question

我有一组整数或示例:{1,3,4,5,10} 现在我想要最大(最大 = 大多数元素)子集，其中每个元素与其他元素的距离/差异最小。

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

{1,3,5,10}

或对于距离 3:

{1,5,10}

是否存在解决该问题的(良好/高效)算法？

Answer 1

这绝对不是 NP 完全问题。

其实是经典的特例Interval Scheduling问题，而在正常的Interval Scheduling问题中，长度是不固定的

在你的问题中，你可以看到每个数字是一个间隔的开始时间，每个间隔都有你的“最小距离”作为间隔长度。

每个区间都有一个结束时间，即开始时间+区间长度

所以解决方案是

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

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

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

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