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
- In jedem Fall, wann wird dein Platz in der Schlange festgelegt: wenn du fragst, oder wenn die Sache frei wird?
- Was passiert mit einer Person, die nicht erscheint, und wie lange bekommt sie?
- Was passiert mit der Sache, während sie darauf wartet, dass sie jemand abholt?
- 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)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:
- 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.
- 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.
- Ein Angebot, das zum Zeitpunkt
ogemacht wurde, kann währendt < o + 120beansprucht werden. Ein Anspruch ohne aktives Angebot für diese Person und dieses Modell wird ignoriert. - An
o + 120läuft ein nicht beanspruchtes Angebot ab und das Telefon wird in diesem Moment wieder frei (Regel 2). - A behauptet zum Zeitpunkt
tbeginnt ein Kredit; das Telefon wird beit + 480. freigegeben. - 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.
(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.
Dieser Browser blockiert Cookies für learn.floati.life, daher können hier beendigte Lektionen nicht in der richtigen Reihenfolge geöffnet werden. Erlaube Cookies für diese Seite und lade sie neu.