algorithm - 在区间 : does this approach work? 中寻找点的替代贪婪策略

Question

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

You are given a collection of intervals. Find the smallest number of points such that each interval contains at least one point.

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

然而，我也想到可以通过选择一次消除更多间隔的点来解决这个问题。我知道这个想法不对，但我找不到任何反例。谁能帮我找到这个策略的反例？

Answer 1

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

采取间隔:

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

Greedy 会在 5 中放一个点，因为它有最多的间隔(除两个以外的所有间隔)然后它会在间隔 [1, 4] 的某处放一个点，在间隔中放另一个点[8, 12]。

贪心的答案是3，但最优的办法是4中放1点，8中放1点，它们都会被覆盖。

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