シラバス レッスン 148 中 50 · 借りてきた仕組み
借りてきた仕組み

取り置きの列を借りる:公平な予約

なぜ大切か いちから作った予約のシステムは、いちばん早くクリックした人に報いがちで、ひとりの来ない人が全員をふさぐのを許しがちです。毎日人々に乏しいものを配る場所は、ずっと前にもっと良い設計に落ち着きました。

3 つのカウンター

図書館の取り置き。貸し出し中の本に予約を入れます。1 冊が戻ると、それは予約の列の最初の人に行き、その人は知らせと、受け取りに来る数日間を得ます。来なければ、その本は次の人に行き、最初の人は自分の場所を失います。

呼び出しベル付きのレストランの順番待ち。名前を伝えてベルを受け取ります。テーブルが空くと、次の組が呼ばれ、5 分以内に案内の台に着かなければテーブルは次の組に行きます。

総菜屋のカウンターの整理券。番号を取ります。自分の番号が呼ばれたときにいなければ、次の番号が呼ばれます。新しい券を、列の後ろで取れます。

コードの前に比べる

  1. それぞれで、列の中の場所はいつ決まる:頼んだときか、ものが空いたときか?
  2. 来ない人はどうなり、どれだけの時間を得る?
  3. 誰かが受け取りに来るのを待つ間、ものはどうなる?
  4. 本にもテーブルにも肉にも触れない一文で、共有する規則を述べる。

目的の問題

モバイルのチームが、テスト用の電話の小さなラボを共有しています。エンジニアは機種を頼み、その機種の電話が空くとそれが勧められ、2 時間以内にラボのアプリで受け取らなければなりません。受け取った電話は 8 時間の枠で予約され、それから自動で戻ります。今のアプリは、空いた電話を最初に「受け取る」を押した人に渡し、人々はそれを押すスクリプトを書き始めています。

stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
          ("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events)   # -> [("ana", "dev1", 30)]  (ben is not first)
あなたの番

loans(stock, events) を書いてください。stock は (device_id, model) を並べ、時刻 0 ではすべて空いています。events は ("request", t, person, model) か ("claim", t, person, model) で、分の時刻 t で並べてあります。規則:

  1. それぞれの機種には頼んだ順のキューがあります。その人がすでにその機種のキューにいるか、その機種の勧めを持っているなら、頼みは無視されます。
  2. 空いた電話は、その機種のキューの最初の人に勧められます(その人はキューを離れます)。誰もキューにいなければ棚で待ち、その機種の後の頼みがすぐにそれを得ます。棚にいくつかあれば、最も小さな端末の ID を勧めます。
  3. 時刻 o にした勧めは、t < o + 120 の間受け取れます。その人と機種について生きた勧めのない受け取りは無視されます。
  4. o + 120 に、受け取られていない勧めは失効し、電話はその瞬間にまた空きます(規則 2)。
  5. 時刻 t の受け取りで貸し出しが始まり、電話は t + 480 に空きます。
  6. イベントの時刻以前に期限の来る失効と返却は、時刻の順、それから端末の ID の順に、それより前に起こります。
受け取られた順に、貸し出しを (person, device_id, claim_time) として返してください。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。