获取整数最大的子集具有一定的最小距离/差异 [英] Get largest Subset of Integers with certain minimum distance/difference

问题描述

我有一组整数或例子：{1,3,4,5,10}现在我想最大的（最大=大部分元素）的子集，其中每个元素都有一个最小距离/区别彼此的元素<。 / P>

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

{1,3,5,10}

或距离3：

{1,5,10}

做了（好/高效）算法存在解决这个问题？

解决方案

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

实际上它是经典间隔调度的问题，而在正常区间调度问题，长度不固定

在这里，你的问题，你可以查看每个数字都是一个区间的开始时间，并且每个间隔有你的最小距离作为间隔长度。

每个间隔具有一个完成时间，也就是开始时间+间隔长度

因此​​，解决方案是

1排序所有完成的时间间隔。

2，通过他们去的排序顺序一个接一个，间隔加入到这是与结果集中所有现有的间隔兼容的结果集。

这个解决方案是最佳的，有O（nlogn）的时间复杂度。

您可以找到的证据和信息关于其他贪婪算法在上面的链接。

i have a Set of Integers or example: {1,3,4,5,10} now i want the biggest (biggest = most elements) Subset where each element has a minimum distance/difference to each other element.

For example with the Set {1,3,4,5,10} and minimum distance 2 a result could be:

{1,3,5,10}

or for distance 3:

{1,5,10}

Does a (good/efficient) algorithm exist to solve that problem ?

解决方案

This is definitely not a NP-complete problem.

Actually it is a special case of the classic Interval Scheduling problem, while in normal Interval Scheduling problem, the length is not fixed

Here in your problem, you can view each number is the start time of an interval, and each interval have your "minimum distance" as the interval length.

Each interval has a finish time, which is start time + interval length

So the solution would be

1 Sort all the interval by finish time.

2 Go through them in the sorted order one by one, add the interval to the result set which is compatible with all existing intervals in the result set.

This solution is optimal and have O(nlogn) time complexity.

You can find the proof and info about other greedy algorithm in the link above.

这篇关于获取整数最大的子集具有一定的最小距离/差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！