发现其中涵盖整组间隔点的最低数量？ [英] Finding minimum number of points which covers entire set of intervals?

问题描述

给定一组间隔 [X，Y]其中0℃的= X，Y＆LT; = 2000 如何找到可以覆盖点的最低数量（即每间隔应包含在所得组点的至少一个点）所有间隔？

例如：

 给定的时间间隔：
    [2,5]
    [3,7]
    [7,10]
 

那么答案应该是2的分 X = 3，X = 7 是一个解决方案（需覆盖所有的间隔点的最小数目）。

解决方案

您可以使用一个贪心算法：

1. 由他们的最终积分排序的所有区间（顺序递增）。

2. 迭代周期的有序数组。当的时间间隔已经过去，有两种选择：

   1. 在它已经涵盖了一些问题。任何东西都不应在这种情况下进行。
   2. 这不是盖的呢。然后这个时间间隔的结束点应该插入到所得到的集合。

该算法生成的结果集是最优的。

Given a set of intervals [x,y] where 0 <= x,y <= 2000 how to find minimum number of points which can cover(i.e. Every interval should contain at least one point in resultant set of points) all intervals?

example:

Given Set of intervals:
    [2,5]
    [3,7]
    [7,10]

then answer should be 2 (minimum number of points required to cover all intervals) as points x=3,x=7 is one solution.

解决方案

You can use a greedy algorithm:

1. Sort all intervals by their end points(in increasing order).

2. Iterate over a sorted array of intervals. When an interval is over, there are two options:

   1. It is already covered by some point. Nothing should be done in this case.
   2. It is not covered yet. Then the end point of this interval should be inserted into to the resulting set.

The resulting set generated by this algorithm is optimal.

这篇关于发现其中涵盖整组间隔点的最低数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！