一种数字分配算法

Question

我正在创建一个预订系统，允许预订特定数量的房间/座位。假设用户可以预订编号为1-100的座位/房间。我的讲师建议我使用一种算法，从经济上划分预订号，以便将未售出的座位保持在最低限度。例如，如果有10个空位：

用户1预订4个座位。给定(编号1-4)。用户2预订1个座位。给定(第5号)。用户3预订4个座位。给定(编号6-9)。然后用户2取消。释放(第5位)。然后用户4想要预订2个座位，但唯一可用的座位是5到10个(不在一起，所以他们不预订)。

我的讲师说这个问题有一个通用的算法，但记不住名字了。我想这就像磁盘上的数据所使用的算法。

有什么想法吗？非常感谢。

Answer 1

没有算法可以保证最优性。

以你的例子为例。为了确保你得到最好的设置，你需要知道谁会取消，以确保他们在空闲空间旁边，这样空闲空间是连续的(并且你可以预订更多)。空闲空间旁边只能有2个预约。除非你能展望未来，说出3个预订中的哪一个不会被取消，否则你就有可能犯错误，没有最佳的分配。

您可以尝试类似于分配技术(malloc)的方法，尝试在最小的可用空间中容纳新的预订。如果你有更多关于预订的信息(可能会被取消)，你可以尝试做出更明智的选择(比如重复预订，就像他们在航空公司做的那样)。如果不能做到这一点，如果您能够重新分配预订(这就是java垃圾收集器在主要压缩上所做的)，那么您仍然可以从系统中挤出更多空间。