Conteúdo do curso Lição 50 de 148 · Máquinas emprestadas
Máquinas emprestadas

Pegue a fila de espera: reservas justas

Por que isso importa Sistemas de reserva feitos do zero costumam premiar quem clica mais rápido, ou deixam alguém que não aparece bloquear todo mundo. Lugares que distribuem coisas escassas para pessoas todos os dias chegaram a um desenho melhor há muito tempo.

Três balcões

A reserva da biblioteca. Você reserva um livro que está emprestado. Quando um exemplar volta, ele vai para a primeira pessoa da fila de reservas, que recebe uma mensagem e alguns dias para buscá-lo. Se ela não vier, o exemplar vai para a próxima pessoa, e a primeira perde o lugar.

A lista de espera do restaurante com pager. Você dá seu nome e recebe um pager. Quando uma mesa fica livre, o próximo grupo é chamado e tem cinco minutos para chegar ao balcão da recepção, ou a mesa vai para o grupo seguinte.

A senha do balcão de frios. Você pega uma senha. Quando seu número é chamado e você não está lá, chamam o próximo número. Você pode pegar uma senha nova, no fim da fila.

Compare antes de programar

  1. Em cada um, quando seu lugar na fila é definido: quando você pede, ou quando a coisa fica livre?
  2. O que acontece com quem não aparece, e quanto tempo essa pessoa tem?
  3. O que acontece com a coisa enquanto ela espera alguém vir buscá-la?
  4. Diga a regra comum em uma frase que não mencione livros, mesas nem frios.

O alvo

O time mobile compartilha um pequeno laboratório de celulares de teste. Engenheiros pedem um modelo; quando um celular desse modelo está livre, ele é oferecido a eles, e eles precisam retirá-lo no app do laboratório em até duas horas. Um celular retirado fica reservado por um turno de oito horas e depois volta automaticamente. Hoje o app dá um celular livre para quem apertar "claim" primeiro, e as pessoas começaram a escrever scripts para apertar o botão.

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)
Sua vez

Escreva loans(stock, events). stock lista (device_id, model), todos gratuitos no tempo 0. events são ("request", t, person, model) ou ("claim", t, person, model), ordenados pelo tempo t em minutos. As regras:

  1. Cada modelo tem uma fila na ordem de solicitação. Uma solicitação é ignorada se aquela pessoa já estiver na fila ou segurando uma oferta para aquele modelo.
  2. Um telefone
  3. A gratuito é oferecido à primeira pessoa na fila do seu modelo (elas saem da fila). Se ninguém estiver na fila, ele espera na prateleira, e uma solicitação posterior para esse modelo o recebe de uma vez. Com vários na prateleira, ofereça o id do dispositivo menor.
  4. Uma oferta feita no tempo o pode ser reivindicada enquanto t < o + 120. Uma reivindicação sem oferta ativa para aquela pessoa e modelo é ignorada.
  5. Em o + 120 uma oferta não reivindicada expira e o telefone fica livre novamente naquele momento (regra 2).
  6. A afirma que no momento t começa um empréstimo; o telefone é liberado em t + 480.
  7. Lapses e retornos devidos no momento ou antes de um evento acontecem antes dele, em ordem de tempo, depois pelo id do dispositivo.
Retorne os empréstimos como (person, device_id, claim_time) na ordem em que foram solicitados.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.