在 k 次尝试中满足最大客人数（时间间隔）

Question

有派对正在进行，给定每位客人参加派对的时间间隔。我可以进入宴会厅 k 次。现在我应该选择 k 个时间实例，以便我会见最多的客人

n - 没有。客人 k - 不。尝试次数

例如：对于 n=5 和 k=2

给定5位客人的间隔[1,3] [4,8] [1,5] [6,8] [4,8] 在 time=1 时，我可以遇到第 1 位和第 3 位客人，在 time=6 时，我可以遇到第 2、4 和 5 位客人。所以我可以在 2 次尝试中最多遇到 5 位客人。我失败的方法：

使用间隔树找到最大重叠点，删除该点的间隔并第二次执行相同操作。它失败了，因为它只给出了 maximum guest 的点，就像我在这个例子中得到的 time=4 一样。这是一个糟糕的选择，因为那样我只能会见 4 位客人。（3 在时间=4 & 1 在时间=1 或时间=6）所以我认为这是动态规划，现在我很震惊。给我一个算法或解决方案或给我建议。提前致谢

Answer 1

嗯，我会建议去动态规划。您可以很容易地检查 "the best time" 进入宴会厅的时间是某人的时间到了。在您的示例中，它将是 3,5 和 8。然后您要做的是计算从中取 2 的最佳可能场景（我仍在根据您的示例解决它，因为我认为这将是最好的解释）。在这里你可以计算如果你先取 3，然后 5，然后 8 并使用相同的递归计算它们会是什么。您可以将花费的时间设置为一组以避免重复，并且在完成 k 步后只需检查其大小，最大的一个就是解决方案。

Answer 2

建立有人进来的时间点列表（或类似的有人离开房间的时间点，就像@Ajris 建议的那样）。这里的时间是 1,4,6

建个图（这个时刻是二分有向的），左边是嘉宾，右边是时间点。对每一位客人在他在房间的时间点做边。这里的边是：

 g1: t1
 g2: t4, t6
 g3  t1, t4
 g4: t6
 g5: t4 ,t6

现在向客人添加辅助顶点S'，并向所有客人添加具有单位容量的边（图不是更二分的，只是有向的）。在 S' 左边再添加一个顶点 S（源），并使边 S-S' 的容量为 K

同时将目标顶点T添加到times中，并从每个时间点（容量为K）添加边。

现在用 any available algorithm

解决 S-T source-sink 对的最大整数流问题

在 k 次尝试中满足最大客人数（时间间隔）

Meeting maximum guests(time-interval) in k attempts

algorithm

dynamic-programming

intervals