一尘不染

给定一组间隔,找到需要放置的最小点数,以便每个间隔中都有一个点

algorithm

假设给定了一组间隔,每个间隔的开始时间为s下标i,结束时间为f下标i。找到每个间隔都有一个点需要放置的最小点数。

我正在尝试找到一种可以解决此问题的算法。当一个重叠两个间隔的间隔(即从一个间隔的一半开始到另一个间隔的一半结束)中包含一个间隔时,我会陷入困境。

谢谢


阅读 286

收藏
2020-07-28

共1个答案

一尘不染

  1. 删除完全包含较小间隔的所有间隔。可以这样做是因为,如果满足较小的间隔,则还必须满足较大的间隔。
  2. 按s_i对间隔进行排序。
  3. 从第一个间隔开始:在f_i处放置一个点。这将满足第一个间隔及其重叠的任何间隔。
  4. 按排序顺序继续到下一个尚不包含点的间隔,然后将点放置在f_i处。
  5. 重复。
2020-07-28