K次尝试中的最大访客数(时间间隔) [英] Meeting maximum guests(time-interval) in k attempts

问题描述

聚会正在进行，给出了每一位客人参加聚会的时间间隔。我可以去派对厅k次。现在我应该选择k个时间实例，这样我就可以遇到最多的客人

n-不。客人的数量 不是。尝试次数

示例：对于n=5&；k=2

给定5个客人的间隔[1，3][4，8][1，5][6，8][4，8] 在时间=1时，我可以会见第一位和第三位客人；在时间=6时，我可以会见第二位、第四位和第五位客人。因此，我在两次尝试中最多可以会见五位客人。 我失败的方法：

1. 使用区间树查找最大重叠点，删除该点上的区间&再次执行相同操作。它失败了，因为它只给出了最大客户数，如本例中的time=4。这是个糟糕的选择，因为那样我只能见4个客人。(3 at time=4&；1 at time=1或time=6) 所以我认为这是一个动态规划&现在我很吃惊。 给我或建议我一个算法或解决方案。提前感谢

推荐答案

嗯，我建议使用动态编程。你可以很容易地发现，进入派对房间的"最佳时间"就是某人的时间到了。在你的例子中，它应该是3，5和8。然后你要做的就是计算出从它取2的最佳可能场景(我仍然在你的例子上解决它，因为我认为这是最好的解释)。在这里，你可以计算，如果你取3，然后是5，然后是8，然后用同样的递归来计算它们。您可以将拍摄次数设置在集合中以避免重复，完成k步后只需检查它的大小，最大的就是解决方案。

这篇关于K次尝试中的最大访客数(时间间隔)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！