寻找覆盖整个间隔的最小点数？

一尘不染

algorithm

给定一组间隔， [x,y] where 0 <= x,y <= 2000如何找到可以覆盖所有间隔的最小点数（即，每个间隔应在结果点集中至少包含一个点）？

例：

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

那么答案应该是2（涵盖所有间隔所需的最少分数），因为分数x=3,x=7是一种解决方案。

阅读 246

2020-07-28

共1个答案

一尘不染

您可以使用贪婪算法：

将所有间隔按其端点排序（升序）。
遍历间隔的排序数组。间隔结束后，有两种选择：
1. 它已经被某些方面覆盖。在这种情况下，不应采取任何措施。
2. 尚未涵盖。然后，应将此间隔的终点插入到结果集中。

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

2020-07-28