algorithm - 是否有 "booking rooms with the least room switches"的算法解决方案的名称？

Question

我正在与一位同事讨论我们部署的一款软件遇到的问题，他提到这与一段时间内预订房间的概念问题有何相似之处，算法应该输出房间需要最少开关的预订(因此，例如，最佳解决方案可能是在一个房间停留 3 天，其余时间在另一个房间，只需要两次开关)。

算法中有这样的问题的名称吗？

Answer 1

最初我发布了一些关于 minimum set cover problem 的内容.虽然您可以将您的问题描述为最小集合覆盖问题，但如果我们假设“房间预订”是连续几天的，您的问题可以用不同的问题来更简洁地描述。

区间覆盖问题¹ 由一个大区间(称为 (a,b))和一堆子区间(称为 (a _i, b_i)).我们的目标是用尽可能少的子区间覆盖一个大区间。

Finding the minimal coverage of an interval with subintervals是大约 5 年前发布的一个问题，它要求一个有效的解决方案，接受的答案表明贪婪的解决方案是最优的。在房间预订的情况下，“贪婪的解决方案”基本上是从时间段的开始开始，并始终选择最晚结束日期的预订。

当然这个问题的想法是每个“子间隔”都是一个预订，所以我们需要的子间隔越少，预订就越少，因此我们需要的“开关”也就越少。

---

^{1 实际上我不是 100% 确定这是正确的名称，但如果你说“间隔覆盖问题”，听众可能会想到同样的事情。}