Prendi in prestito la coda delle prenotazioni: prenotazioni eque
Perché è importante I sistemi di prenotazione costruiti da zero tendono a premiare chi clicca più in fretta, o lasciano che una persona che non si presenta blocchi tutti. I posti che distribuiscono ogni giorno cose scarse alle persone hanno scelto da tempo un progetto migliore.
Tre banconi
Una prenotazione in biblioteca. Prenoti un libro che è in prestito. Quando una copia rientra, va alla prima persona nella coda delle prenotazioni, che riceve un messaggio e qualche giorno per ritirarla. Se non viene, la copia passa alla persona successiva, e la prima perde il suo posto.
La lista d'attesa di un ristorante con il cercapersone. Dai il tuo nome e ricevi un cercapersone. Quando un tavolo si libera, il gruppo successivo viene chiamato e ha cinque minuti per arrivare al banco dell'accoglienza, altrimenti il tavolo va al gruppo successivo.
Il biglietto del banco gastronomia. Prendi un numero. Quando il tuo numero viene chiamato e non ci sei, viene chiamato il numero successivo. Puoi prendere un biglietto nuovo, in fondo.
Confronta prima di scrivere codice
- In ciascuno, quando viene fissato il tuo posto in fila: quando chiedi, o quando la cosa si libera?
- Che cosa succede a una persona che non si presenta, e quanto tempo ha?
- Che cosa succede alla cosa mentre aspetta che qualcuno la ritiri?
- Esprimi la regola condivisa in una frase che non menzioni libri, tavoli o affettati.
Il problema di arrivo
Il team mobile condivide un piccolo laboratorio di telefoni di prova. Gli ingegneri chiedono un modello; quando un telefono di quel modello è libero, viene offerto loro, e devono prenotarlo nell'app del laboratorio entro due ore. Un telefono prenotato è assegnato per una fascia di otto ore e poi torna disponibile da solo. Oggi l'app dà un telefono libero a chi preme "prenota" per primo, e le persone hanno iniziato a scrivere script per premerlo.
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)Scrivi loans(stock, events). stock elenca coppie (device_id, model), tutte libere al tempo 0. events sono ("request", t, person, model) o ("claim", t, person, model), ordinati per tempo t in minuti. Le regole:
- Ogni modello ha una coda in ordine di richiesta. Una richiesta viene ignorata se quella persona è già in coda per quel modello, o ha già un'offerta su quel modello.
- Un telefono libero viene offerto alla prima persona nella coda del suo modello (che esce dalla coda). Se nessuno è in coda resta sullo scaffale, e una richiesta successiva per quel modello lo ottiene subito. Con più telefoni sullo scaffale, offri il device id più piccolo.
- Un'offerta fatta al tempo
osi può prenotare finchét < o + 120. Una prenotazione senza un'offerta valida per quella persona e quel modello viene ignorata. - A
o + 120un'offerta non prenotata scade e il telefono torna libero in quel momento (regola 2). - Una prenotazione al tempo
tavvia un prestito; il telefono torna libero at + 480. - Le scadenze e i rientri dovuti entro il tempo di un evento avvengono prima di esso, in ordine di tempo, poi di device id.
(person, device_id, claim_time) nell'ordine in cui sono stati prenotati.
Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione
Questo esercizio si apre presto
Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.
Questo browser blocca i cookie per learn.floati.life, quindi le lezioni che hai finito qui non si possono aprire in ordine. Consenti i cookie per questo sito e ricarica.