何らかの番号割り当てアルゴリズム

Question

私は、特定の数の部屋/座席を予約できる予約システムを作成しています。 1〜100の番号を付けられた座席/部屋を予約できるとします。私の講師は、予約番号を経済的に分けるアルゴリズムを使って、売れ残った座席が最小限に抑えられるよう提案しました。たとえば、10席がある場合は、

ユーザ1冊4席です。与えられた（1-4項）。 ユーザー2冊1席。与えられた（no 5）。 ユーザー3冊4席与えられた（no 6-9）。 ユーザ2がキャンセルされます。解放する（5番）。 ユーザー4は2席の予約を希望しますが、唯一の席は5 & 10です（一緒には予約できません）。

私の講師は、この問題に共通のアルゴリズムが存在するが、その名前を覚えていないと述べました。私はそれがディスク上のデータに使用されるアルゴリズムのようだと思います。

アイデア？ 多くのありがとうございます。

Answer 1

最適性を保証するアルゴリズムはありません。

例を挙げてください。最高のセットアップを得るためには、空きスペースの隣にいることを確認するために誰がキャンセルするのかを知る必要があるため、空きスペースは連続しています（さらに予約できるようになります）。空き領域の隣に2つの予約のみがあります。未来を見て、3つの予約のうちのどの予約がキャンセルされないかを言わない限り、あなたは間違いを犯し、最適な割り当てをしていないチャンスを走ります。

利用可能な最小のスペースに新しい予約を適用しようとする割り当て手法（malloc）に似たものを試すことができます。予約に関する詳細情報がある場合（キャンセルされる可能性があります）、スマートな選択をすることができます（航空会社と同じようにダブル予約など）。 予約を再割当てすることができれば、システムからさらに絞り出すことができなくなります（これは、Javaガベージコレクタが主要な圧縮で行うことです）。