algorithm - 住宿/日票问题的最佳拟合调度算法？

Question

我有一个调度问题，我正在尝试找出最适合使用的算法。

酒店拥有主题公园，是入住酒店游客的一大亮点。但是，对于想去主题公园的游客，酒店的房间多于一日通行证。因此在高峰期，有些人可能无法去主题公园。

我们希望每位游客至少有 1 次参观主题公园的机会。

如果有争议，我们希望将日间通行证提供给在酒店停留时间较长的游客。

谁能为我指出最适合问题的算法的正确方向？

不，这不是家庭作业。 :)

提前致谢。

Answer 1

您可以使用 Priority Queue (PQ)。每天您将客户放入您的 (PQ) 计算优先级为 p = 1/r，其中 r 是该客人在您酒店的剩余天数。这样，您每天都会将您的 n 通行证赠送给那些在您的酒店停留天数较少的 n 位顾客(如果一位顾客只剩下 1 天的停留时间，她/他必须优先获得通行证，因为只有一种可能性)。如果您有多个具有相同 p 的客户，那么您可以通过查看他们在您酒店停留的总天数来从他们中进行选择，并且您会偏向于那些停留时间更长的客户。