Lehrplan Lektion 50 von 148 · Geliehene Maschinen
Geliehene Maschinen

Leihe dir die hold queue: faire Reservierungen

Warum das wichtig istReservierungssysteme, die von Grund auf neu gebaut werden, neigen dazu, denjenigen zu belohnen, der am schnellsten klickt, oder lassen eine Person ohne Erscheinen alle blockieren. Orte, die täglich knappe Dinge an Menschen verteilen, haben sich vor langer Zeit für ein besseres Design entschieden.

Drei Zähler

A Bibliothek-Reservierung. Du setzt eine Reservierung für ein Buch, das ausgeliehen ist. Wenn ein Exemplar zurückkommt, geht es an die erste Person in der Reservierungsliste. Diese Person erhält eine Nachricht und hat einige Tage Zeit, es abzuholen. Wenn sie nicht kommen, geht das Exemplar an die nächste Person und die erste Person verliert ihren Platz.

A Restaurant-Warteliste mit einem Buzzer. Du gibst deinen Namen an und erhältst einen Buzzer. Wenn ein Tisch frei wird, wird die nächste Gruppe benachrichtigt und hat fünf Minuten Zeit, zum Host Stand zu gelangen, oder der Tisch geht an die nächste Gruppe.

Das Ticket am Verkaufstresen. Du nimmst eine Nummer. Wenn deine Nummer gerufen wird und du nicht da bist, wird die nächste Nummer gerufen. Du kannst hinten ein neues Ticket nehmen.

Vergleiche, bevor du programmierst

  1. In jedem Fall, wann wird dein Platz in der Schlange festgelegt: wenn du fragst, oder wenn die Sache frei wird?
  2. Was passiert mit einer Person, die nicht erscheint, und wie lange bekommt sie?
  3. Was passiert mit der Sache, während sie darauf wartet, dass sie jemand abholt?
  4. Nenne die gemeinsame Regel in einem Satz, der keine Bücher, Tabellen oder Fleisch erwähnt.

Das Ziel

Das mobile Team teilt sich ein kleines Labor mit Testtelefonen. Ingenieure fordern ein Modell an; wenn ein Telefon dieses Modells frei wird, wird es ihnen angeboten, und sie müssen es innerhalb von zwei Stunden in der Labor-App beanspruchen. Ein beanspruchtes Telefon ist für einen achtstündigen Slot gebucht und kommt dann automatisch zurück. Heute gibt die App ein freies Telefon an denjenigen, der zuerst auf "beanspruchen" drückt, und die Leute haben angefangen, Skripte zu schreiben, um es zu drücken.

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)
Du bist dran

Schreibe loans(stock, events). stock listet (device_id, model) auf, alle frei zum Zeitpunkt 0. events sind ("request", t, person, model) oder ("claim", t, person, model), sortiert nach Zeit t in Minuten. Die Regeln:

  1. Jedes Modell hat eine Warteschlange in der Reihenfolge der Anfragen. Eine Anfrage wird ignoriert, wenn diese Person bereits für dieses Modell in der Warteschlange steht oder ein Angebot für dieses Modell hält.
  2. A kostenloses Telefon wird der ersten Person in der Schlange ihres Modells angeboten (sie verlassen die Schlange). Wenn niemand in der Schlange ist, wartet es im Regal, und eine spätere Anfrage für dieses Modell erhält es sofort. Bei mehreren im Regal biete die kleinste device id an.
  3. Ein Angebot, das zum Zeitpunkt o gemacht wurde, kann während t < o + 120 beansprucht werden. Ein Anspruch ohne aktives Angebot für diese Person und dieses Modell wird ignoriert.
  4. An o + 120 läuft ein nicht beanspruchtes Angebot ab und das Telefon wird in diesem Moment wieder frei (Regel 2).
  5. A behauptet zum Zeitpunkt t beginnt ein Kredit; das Telefon wird bei t + 480.
  6. freigegeben.
  7. Lapses und returns, die zum Zeitpunkt eines Ereignisses oder davor fällig sind, treten vor ihm auf, sortiert nach Zeit und dann nach device id.
Gib die loans als (person, device_id, claim_time) in der Reihenfolge zurück, in der sie beansprucht wurden.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.