在区间内寻找点的替代贪婪策略：这种方法行得通吗？

Question

我正在尝试解决以下问题：

您将获得间隔的集合。找到最少的点，以使每个间隔至少包含一个点。

我知道此问题的一种解决方案是按时间间隔对时间间隔进行排序，然后贪婪地反复选择尚未覆盖的最早时间间隔的终点并将其添加到结果中。

但是，我也想到可以通过选择一次消除更多间隔的点来解决。我知道这个想法是不正确的，但是我找不到任何反例。有人可以帮我找到这种策略的反例吗？

Answer 1

这里是一个假设包含间隔的示例。

间隔时间：

[1, 4], [2, 5], [3, 6], [4, 7], [5, 8], [5, 9], [5, 10], [8, 12]

Greedy将一个点放置在5中，因为它具有最大的间隔（除了两个以外，其他所有点），然后它将在点[1, 4]中放置一个点，在间隔[8, 12]中放置另一个点。

Greedy的答案是3。但是最佳方法是将1分放在4中，将1分放在8中，然后将它们全部覆盖。

编辑：在纸上画出间隔以便更好地理解。

Answer 2

[-----]         [-----]
[------------]
        [-------------]
[------------]
        [-------------]