Kurrikulum Leson 50 van 148 · Geleende masjiene
Geleende masjiene

Leen die hold queue: regverdige reservasies

Waarom dit saak maak Reservasiesisteme wat van nuut af gebou word, beloon gewoonlik wie die vinnigste klik, of laat een persoon wat nie verskyn nie almal blokkeer. Plekke wat elke dag skaars goed aan mense uitdeel, het lank gelede op 'n beter ontwerp besluit.

Drie tellers

A biblioteek-hou. Jy plaas 'n hou op 'n boek wat uit is. Wanneer 'n kopie terugkom, gaan dit na die eerste persoon in die hou-wenseel. Daardie persoon kry 'n boodskap en 'n paar dae om dit te kom haal. As hulle nie kom nie, gaan die kopie na die volgende persoon en die eerste persoon verloor hul plek.

'n restaurant-waglys met 'n binner. Jy gee jou naam en kry 'n binner. Wanneer 'n tafel vry word, word die volgende groep gebinner en het hulle vyf minute om by die gasheer-toonbank te kom, anders gaan die tafel na die volgende groep.

Die deli-teller kaartjie. Jy neem 'n nommer. Wanneer jou nommer geroep word en jy nie daar is nie, word die volgende nommer geroep. Jy kan 'n nuwe kaartjie by die agterkant neem.

Vergelyk voor jy kodeer

  1. In elk een, wanneer word jou plek in die ry vas: wanneer jy vra, of wanneer die ding vry word?
  2. Wat gebeur met 'n persoon wat nie opdaag nie, en hoe lank kry hulle?
  3. Wat gebeur met die ding terwyl dit wag dat iemand dit kom haal?
  4. Noem die gedeelde reël in een sin wat geen boeke, tafels of vleis noem nie.

Die teiken

Die mobiele span deel 'n klein laboratorium van toetsfone. Ingenieurs versoek 'n model; wanneer 'n foon van daardie model vry is, word dit aan hulle aangebied, en hulle moet dit binne twee uur in die lab app eis. 'n Geëiste foon word vir 'n agtuur slot besprek en kom dan outomaties terug. Vandag gee die app 'n vrye foon vir wie om die eerste "claim" druk, en mense het begin om scripts te skryf om dit te druk.

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)
Jou beurt

Skryf loans(stock, events). stock lys (device_id, model) op, al is hulle vry teen tyd 0. events is ("request", t, person, model) of ("claim", t, person, model), gesorteer volgens tyd t in minute. Die reëls:

  1. Elke model het 'n ry in versoekorde. 'n Versoek word geïgnoreer as daardie persoon reeds vir daardie model in die ry is, of 'n aanbod op daardie model hou.
  2. A gratis foon word aangebied aan die eerste persoon in die ry vir daardie model (hulle verlaat die ry). As niemand in die ry is nie, wag dit op die rak, en 'n latere versoek vir daardie model kry dit dadelik. Met verskeie op die rak, bied die kleinste device id aan.
  3. 'n aanbod wat tydens o gemaak is, kan geëis word terwyl t < o + 120. 'n Eis sonder 'n aktiewe aanbod vir daardie persoon en model word geïgnoreer.
  4. Wanneer o + 120 'n oneisbare aanbod verval en die foon op daardie oomblik weer vry word (reël 2).
  5. A eis op tyd t begin 'n lening; die foon word vrygestel by t + 480.
  6. Lapses en returns wat teen of voor 'n gebeurtenis se tyd verval, gebeur voor dit, in volgorde van tyd, dan toestel id.
Gee die leninge terug as (person, device_id, claim_time) in die volgorde waarin hulle geëis is.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.