Temario Lección 50 de 148 · Máquinas prestadas
Máquinas prestadas

Toma prestada la cola de reservas: reservas justas

Por qué importa Los sistemas de reservas hechos desde cero tienden a premiar a quien hace clic más rápido, o dejan que alguien que no aparece bloquee a todos. Los sitios que reparten cosas escasas a personas todos los días llegaron hace tiempo a un diseño mejor.

Tres mostradores

Una reserva en la biblioteca. Reservas un libro que está prestado. Cuando vuelve un ejemplar, va a la primera persona de la cola de reservas, que recibe un aviso y unos días para recogerlo. Si no viene, el ejemplar pasa a la siguiente persona, y la primera pierde su sitio.

La lista de espera de un restaurante con un avisador. Das tu nombre y te dan un avisador. Cuando se libera una mesa, avisan al siguiente grupo, que tiene cinco minutos para llegar a recepción, o la mesa pasa al siguiente grupo.

El ticket del mostrador de charcutería. Coges un número. Cuando llaman a tu número y no estás, llaman al siguiente. Puedes coger un ticket nuevo, al final.

Compara antes de programar

  1. En cada uno, ¿cuándo se fija tu sitio en la cola: cuando lo pides, o cuando la cosa queda libre?
  2. ¿Qué le pasa a una persona que no aparece, y cuánto tiempo tiene?
  3. ¿Qué le pasa a la cosa mientras espera a que alguien la recoja?
  4. Di la regla común en una frase que no mencione libros, mesas ni embutidos.

El objetivo

El equipo móvil comparte un pequeño laboratorio de teléfonos de prueba. Los ingenieros piden un modelo; cuando queda libre un teléfono de ese modelo, se les ofrece, y tienen que reclamarlo en la app del laboratorio en dos horas. Un teléfono reclamado queda reservado para un turno de ocho horas y luego vuelve solo. Hoy la app da un teléfono libre a quien pulse "reclamar" primero, y la gente ha empezado a escribir scripts para pulsarlo.

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)
Tu turno

Escribe loans(stock, events). stock lista (device_id, model), todos libres en el momento 0. events son ("request", t, person, model) o ("claim", t, person, model), ordenados por tiempo t en minutos. Las reglas:

  1. Cada modelo tiene una cola en orden de petición. Una petición se ignora si esa persona ya está en la cola de ese modelo, o tiene una oferta de él.
  2. Un teléfono libre se ofrece a la primera persona de la cola de su modelo (que sale de la cola). Si no hay nadie en la cola espera en la estantería, y una petición posterior de ese modelo lo recibe al momento. Si hay varios en la estantería, ofrece el device id más pequeño.
  3. Una oferta hecha en el momento o se puede reclamar mientras t < o + 120. Una reclamación sin oferta viva para esa persona y ese modelo se ignora.
  4. En o + 120 una oferta no reclamada caduca y el teléfono vuelve a quedar libre en ese momento (regla 2).
  5. Una reclamación en el momento t empieza un préstamo; el teléfono queda libre en t + 480.
  6. Las caducidades y devoluciones que tocan en el momento de un evento o antes ocurren antes que él, por orden de tiempo y luego de device id.
Devuelve los préstamos como (person, device_id, claim_time) en el orden en que se reclamaron.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.