小编Ark*_*adi的帖子

给定实线上的一组区间和一些参数 d > 0。找到相邻点之间的间隙小于或等于 d 的点序列，使得包含任何点的区间数最小化。为了防止琐碎的解决方案，我们要求序列中的第一个点在第一个间隔之前，而最后一个点在最后一个间隔之后。间隔可以被认为是右开的。

这个问题有名字吗？甚至可能是算法和复杂性界限？

一些背景： 这是由拓扑数据分析中的一个问题引发的，但它似乎很笼统，以至于它可能对其他主题很有趣，例如任务调度（假设工厂每年必须至少关闭一次并希望最小化维护造成的任务数量......）我们正在考虑整数规划和最小削减，但 d 参数不太合适。我们还在 n^2 和 n*logn 时间内实现了近似贪婪解决方案，但它们可能会遇到非常糟糕的局部最优解。

给我看一张图片

我用线画间隔。下图显示了 7 个区间。d 是这样的，您必须至少每四个字符剪切一次。在图表的底部，您会看到图表的两个解决方案（用 x 和 y 标记）。x 穿过顶部的四个区间，而 y 穿过底部的三个区间。y 是最优的。

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

给我看一些代码： 我们应该如何fun在下面的代码片段中定义？

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

在这个小例子中，最优解将削减第一个区间，但不会削减第二个和第三个区间。显然，该算法也应该适用于更复杂的例子。

更严格的测试如下：给定 [0, 100] 上间隔开始时间的均匀分布和 [0, d] 上的长度均匀分布，可以通过规则网格 [0, d, 2d] 计算预期的切割次数, 3d,..] 略低于 0.5*n。最佳解决方案应该更好：

intervals …