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

Question

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

我在试着找一个算法来解决这个问题。当重叠两个区间的区间，即一个区间开始于一个区间的中途，结束于另一个区间的中途，其中包含一个区间时，我就被卡住了。

谢谢

Answer 1

1. 删除所有完全包含较小间隔的间隔。之所以可以这样做，是因为如果满足较小的间隔，则较大的间隔也必须是satisfied.
2. Sort interval by s_i。从第一个间隔开始放置点。这将满足第一个间隔以及与其重叠的任何间隔。
3. 将按排序顺序继续到还不包含点的下一个间隔，并在f_i.
4. Repeat.

放置点

Answer 2

1. 以不递减的上限bound.
2. Initialize a变量most_recent_placed to -inf (小于所有间隔下限的值)的顺序对间隔进行排序。
3. 按排序顺序扫描间隔。对于给定的间隔[a, b]，如果为most_recent_placed < a，则将一个点置于b，并将most_recent_placed设置为most_recent_placed < a

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

Answer 3

这个问题需要一个带有代码的答案。下面是user612112提到的算法的python实现，它比公认的答案中的算法要好一点：

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

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

# 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)