覆盖所有的号码与给定的时间间隔 [英] Covering all the numbers with the given intervals

问题描述

这是对算法大师的问题在那里： - ）

This is a question for the algorithms gurus out there :-)

让取值是一组自然数的间隔可能会重叠，N为号码列表中。

Let S be a set of intervals of the natural numbers that might overlap and N be a list of numbers.

我想找到最小的子集（我们称之为P）的S，使得对每个号码 在我们的名单N，存在P中的至少一个间隔包含它。在P上的间隔允许重叠。

I want to find the smallest subset (let's call P) of S such that for each number in our list N, there exists at least one interval in P that contains it. The intervals in P are allowed to overlap.

简单的例子：

S = {[1..4], [2..7], [3..5], [8..15], [9..13]}
N = [1, 4, 5]
// so P = {[1..4], [2..7]}

我觉得一个动态的算法可能并不总是可行的，因此，如果任何人知道解决这个问题（或类似的一个可以转换成），那将是巨大的。

I think a dynamic algorithm might not work always, so if anybody knows of a solution to this problem (or a similar one that can be converted into), that would be great.

谢谢！

推荐答案

您可以用贪​​心算法做到这一点。

You can do this with a greedy algorithm.

考虑的N点的顺序。

对于每一个点，如果它已经涵盖了一个区间，然后跳过它。

For each point, if it is already covered by an interval then skip it.

另外，考虑到包括该点的时间间隔。在这些间隔，选择一个覆盖大部分未覆盖的点。 （这将是具有最高终点的时间间隔。）

Otherwise, consider the intervals that include the point. Out of these intervals, choose the one that covers the most uncovered points. (This will be the interval with the highest end point.)

1. 第一点是1，覆盖只是1..4所以这个时间加入到我们组。
2. 第二点是4，但它已经涵盖如此继续下去。
3. 第二点是5，覆盖2..7和3..5。选择其中任一让，涵盖所有的点了2台答案。

这篇关于覆盖所有的号码与给定的时间间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！