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

Question

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

我正在尝试找到一种可以解决这个问题的算法.当一个重叠两个间隔的间隔,即在一个间隔的中间开始,在另一个间隔的中间结束时,我会卡在其中.

谢谢

Answer 1

1. 删除任何完全包含较小间隔的间隔.您可以这样做,因为如果满足较小的间隔,则还必须满足较大的间隔.
2. 按s_i排序间隔.
3. 从第一个间隔开始:在f_i处放置一个点.这将满足第一个间隔,以及与其重叠的任何间隔.
4. 按排序顺序继续到下一个尚未包含点的间隔,并在f_i处放置一个点.
5. 重复.

Answer 2

1. 按上限不递减的顺序对区间进行排序。
2. 将变量初始化most_recent_placed为-inf（小于所有区间下限的值）。
3. 按排序顺序扫描间隔。对于给定的间隔[a, b]，如果most_recent_placed < a，则在 处放置一个点b并设置most_recent_placed为b。

这个解 A 是最优的证明是归纳地确定对于任何有效解 B 和任何点x，B 放置的坐标小于x的点数至少与 A 放置的点数一样大x。

Answer 3

这个问题需要用代码来回答。这是user612112提到的算法的python实现，比接受的答案中的要好一点：

1. 初始化一个空的输出点列表
2. 按终点对范围进行排序，并按终点顺序处理它们
3. 对于每个范围，如果最后一个输出点小于范围的开始，则将范围的结束点添加到输出集

请注意，您不需要任何预处理来删除冗余范围，也不需要排序来区分具有相同端点的多个范围。

# given some inclusive ranges
ranges=[(1,5),(2,4),(4,6),(3,7),(5,9),(6,6)]

# sort by the end points
ranges.sort(key=lambda p:p[1])

#generate required points
out=[]
last = None
for r in ranges:
    if last == None or last < r[0]:
        last = r[1]
        out.append(last)

#print answer
print(out)