某種數字分配算法

Question

我正在創建一個允許預訂特定數量的房間/座位的預訂系統。假設用戶可以預訂編號爲1-100的座位/房間。我的講師建議我使用一種經濟地劃分保留數字的算法，以便將未售出的座位保持在最低限度。例如，如果有10個座位可用：

用戶1書4座。鑑於（否1-4）。 用戶2書1個座位。給定（不是5）。 用戶3冊4席。給定（不是6-9）。 用戶2然後取消。釋放（不5）。 用戶4然後想要預訂2個座位，但唯一可用的座位是5 & 10（不在一起，所以他們不預訂）。

我的講師說這個問題存在一個常見的算法，但是不記得名字。我想這就像用於磁盤上數據的算法。

任何想法？ 非常感謝。

Answer 1

沒有保證最優性的算法。

舉一個例子。爲確保獲得最佳設置，您需要知道誰將取消以確保他們位於免費空間旁邊，以便可用空間連續（並且您可以預訂更多）。只有2個預訂可以在免費空間旁邊。除非你可以看看未來，並說出三次預訂中的哪一次不會被取消，否則你將有機會犯錯並且沒有優化分配。

您可以嘗試類似於分配技術（malloc）的嘗試，以嘗試將新預訂納入最小可用空間。如果您有更多有關預訂的信息（它將被取消的概率），您可以嘗試做出更明智的選擇（如重複預訂，就像他們在航空公司所做的那樣）。 如果您可以重新分配預訂（這是java垃圾收集器在主要壓縮中執行的操作），那麼仍然可能擠出更多系統。