Программа курса Урок 50 из 148 · Заимствованные механизмы
Заимствованные механизмы

Заимствуйте очередь резервирования: честные брони

Почему это важно Системы бронирования, построенные с нуля, склонны вознаграждать того, кто кликает быстрее, или позволяют одному неявившемуся блокировать всех. Места, которые каждый день раздают людям дефицитные вещи, давно пришли к лучшему дизайну.

Три стойки

Резерв в библиотеке. Вы ставите в резерв книгу, которая выдана. Когда экземпляр возвращается, он достаётся первому в очереди резерва, который получает сообщение и несколько дней, чтобы его забрать. Если человек не приходит, экземпляр переходит следующему, а первый теряет своё место.

Лист ожидания в ресторане с пейджером. Вы называете имя и получаете пейджер. Когда стол освобождается, вызывают следующую компанию, и у неё есть пять минут, чтобы дойти до стойки администратора, иначе стол достаётся следующей компании.

Талончик у прилавка гастрономии. Вы берёте номер. Когда ваш номер вызывают, а вас нет, вызывают следующий номер. Можно взять новый талончик, в конец.

Сравните, прежде чем писать код

  1. Когда в каждом случае фиксируется ваше место в очереди: когда вы просите или когда вещь освобождается?
  2. Что происходит с тем, кто не пришёл, и сколько времени ему дают?
  3. Что происходит с вещью, пока она ждёт, чтобы её забрали?
  4. Сформулируйте общее правило одним предложением, где нет ни книг, ни столов, ни колбасы.

Цель

Мобильная команда делит небольшую лабораторию тестовых телефонов. Инженеры запрашивают модель; когда телефон этой модели свободен, его предлагают им, и они должны забрать его в приложении лаборатории в течение двух часов. Забранный телефон бронируется на восьмичасовой слот, а затем автоматически возвращается. Сегодня приложение отдаёт свободный телефон тому, кто первым нажмёт "забрать", и люди начали писать скрипты, которые его нажимают.

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)
Твоя очередь

Напишите loans(stock, events). stock перечисляет (device_id, model), все свободны в момент 0. events - это ("request", t, person, model) или ("claim", t, person, model), отсортированные по времени t в минутах. Правила:

  1. У каждой модели есть очередь в порядке запросов. Запрос игнорируется, если этот человек уже стоит в очереди на эту модель или держит на неё предложение.
  2. Свободный телефон предлагается первому человеку в очереди его модели (тот выходит из очереди). Если в очереди никого нет, он ждёт на полке, и более поздний запрос на эту модель получает его сразу. Если на полке несколько, предлагайте наименьший id устройства.
  3. Предложение, сделанное в момент o, можно забрать, пока t < o + 120. Забор без действующего предложения для этого человека и модели игнорируется.
  4. В момент o + 120 незабранное предложение истекает, и телефон снова освобождается в этот момент (правило 2).
  5. Забор в момент t начинает выдачу; телефон освобождается в t + 480.
  6. Истечения и возвраты, приходящиеся на время события или раньше, происходят до него, в порядке времени, затем id устройства.
Верните выдачи как (person, device_id, claim_time) в порядке, в котором их забрали.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.