Programma Les 50 van 148 · Geleende machines
Geleende machines

Leen de hold queue: eerlijke reserveringen

Waarom dit ertoe doet Reservatiesystemen die vanaf nul worden gebouwd belonen vaak degene die het snelst klikt, of laten één no-show iedereen blokkeren. Plekken die elke dag schaarse zaken aan mensen geven kozen lang geleden voor een beter ontwerp.

Drie tellers

A library hold. Je plaatst een hold op een boek dat uitgeleend is. Wanneer een exemplaar terugkomt, gaat het naar de eerste persoon in de hold queue. Deze persoon krijgt een bericht en een paar dagen om het op te halen. Als ze niet komen, gaat het exemplaar naar de volgende persoon en de eerste verliest hun plek.

A wachtlijst voor een restaurant met een binner. Je geeft je naam op en krijgt een binner. Wanneer een tafel vrijkomt, krijgt de volgende groep een seintje en heeft deze vijf minuten om naar de host stand te gaan, anders gaat de tafel naar de volgende groep.

Het bonnetje van de broodjeskraam. Je pakt een nummer. Als jouw nummer wordt geroepen en je bent er niet, wordt het volgende nummer geroepen. Je kunt een nieuw bonnetje pakken, achteraan.

Vergelijk voordat je codeert

  1. In elk geval, wanneer wordt je plek in de rij vastgelegd: wanneer je vraagt, of wanneer het ding vrij wordt?
  2. Wat gebeurt er met een persoon die niet opdaagt, en hoe lang krijgen ze?
  3. Wat gebeurt er met het ding terwijl het wacht tot iemand het ophaalt?
  4. Noem de gedeelde regel in één zin die geen boeken, tafels of vlees noemt.

Het doel

Het mobiele team deelt een klein lab met testtelefoons. Ingenieurs vragen een model aan; wanneer een telefoon van dat model vrij is, wordt deze aan hen aangeboden, en ze moeten deze binnen twee uur claimen in de lab app. Een geclaimde telefoon is geboekt voor een tijdslot van acht uur en komt daarna automatisch terug. Vandaag geeft de app een vrije telefoon aan wie als eerste op "claim" drukt, en mensen zijn begonnen met het schrijven van scripts om erop te drukken.

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)
Jij bent aan de beurt

Schrijf loans(stock, events). stock bevat (device_id, model), allemaal gratis op tijdstip 0. events zijn ("request", t, person, model) of ("claim", t, person, model), gesorteerd op tijd t in minuten. De regels:

  1. Elk model heeft een wachtrij in volgorde van aanvraag. Een aanvraag wordt genegeerd als die persoon al in de wachtrij staat voor dat model, of een aanbod voor dat model heeft.
  2. een gratis telefoon wordt aangeboden aan de eerste persoon in de wachtrij van dat model (ze verlaten de wachtrij). Als er niemand in de wachtrij staat, wacht het op de plank, en een latere aanvraag voor dat model krijgt het meteen. Bij meerdere op de plank, bied het kleinste device id aan.
  3. Een aanbod dat is gedaan op tijd o kan worden geclaimd terwijl t < o + 120. Een claim zonder live aanbod voor die persoon en model wordt genegeerd.
  4. At o + 120 verloopt een niet geclaimd aanbod en de telefoon wordt op dat moment weer vrijgegeven (regel 2).
  5. A claim op het moment t start een lening; de telefoon is vrij bij t + 480.
  6. Lapses en returns die op of voor de tijd van een event vervallen, gebeuren ervoor, gesorteerd op tijd, dan op device id.
Geef de leningen terug als (person, device_id, claim_time) in de volgorde waarin ze zijn opgeëist.

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.