给定一组间隔，找到需要放置的最小点数，以便每个间隔中都有一个点 [英] Given a set of intervals, find the minimum number of points that need to be placed, so that every interval has a point in it

问题描述

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

Suppose you are given a set of intervals, with the starting time of each interval as s subscript i and the finishing time of f subscript i. Find the minimum number of points that need to be placed to that every interval has a point.

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

I'm trying to find an algorithm that would solve this. I'm getting stuck when an interval that overlap two intervals, i.e starts halfway through one interval and ends halfway through another has an interval that is contained in it.

谢谢

推荐答案

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

这篇关于给定一组间隔，找到需要放置的最小点数，以便每个间隔中都有一个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！