Programma Lezione 50 di 148 · Macchine prese in prestito
Macchine prese in prestito

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

  1. In ciascuno, quando viene fissato il tuo posto in fila: quando chiedi, o quando la cosa si libera?
  2. Che cosa succede a una persona che non si presenta, e quanto tempo ha?
  3. Che cosa succede alla cosa mentre aspetta che qualcuno la ritiri?
  4. 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)
Tocca a te

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:

  1. 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.
  2. 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.
  3. Un'offerta fatta al tempo o si può prenotare finché t < o + 120. Una prenotazione senza un'offerta valida per quella persona e quel modello viene ignorata.
  4. A o + 120 un'offerta non prenotata scade e il telefono torna libero in quel momento (regola 2).
  5. Una prenotazione al tempo t avvia un prestito; il telefono torna libero a t + 480.
  6. Le scadenze e i rientri dovuti entro il tempo di un evento avvengono prima di esso, in ordine di tempo, poi di device id.
Restituisci i prestiti come (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.