algorithm - “预订房间开关最少的房间”的算法解决方案有名称吗？

Question

我正在与一位同事讨论我们在部署的软件中遇到的问题，他提到这与在一段时间内预订房间的概念问题很相似，并且算法应该输出需要的房间预订最少的开关（例如，最佳解决方案可能是在一个房间住 3 天，其余的在另一个房间，只需要两个开关）。

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

Answer 1

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

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

找到具有子区间的区间的最小覆盖率是大约 5 年前发布的一个问题，它要求一个有效的解决方案，并且接受的答案表明贪婪解决方案是最优的。在房间预订的情况下，“贪婪的解决方案”基本上是从周期的开始开始，总是选择最晚结束日期的预订。

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

---

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