Müfredat 148 dersinden 50. · Ödünç alınan makineler
Ödünç alınan makineler

Tutma kuyruğunu ödünç al: adil rezervasyonlar

Neden önemliSıfırdan inşa edilen rezervasyon sistemleri genellikle en hızlı tıklayanı ödüllendirir veya bir kişinin gelmemesi herkesi engelleyebilir. Her gün kısıtlı şeyleri insanlara dağıtan yerler çoktan daha iyi bir tasarımda karar kıldı.

Üç sayaç

bir kütüphane rezervasyonu. Dışarıda olan bir kitap için rezervasyon yaparsın. Bir kopya geri geldiğinde, rezervasyon sırasındaki ilk kişiye gider. Bu kişi bir mesaj alır ve kitabı almak için birkaç günü olur. Eğer gelmezlerse, kopya bir sonraki kişiye gider ve ilk kişi sırasını kaybeder.

Buzzerlı bir restoran bekleme listesi. Adını veriyorsun ve bir buzzer alıyorsun. Bir masa boşaldığında, sıradaki gruba buzzer çalıyor ve host standına ulaşmak için beş dakikası oluyor, aksi takdirde masa sıradaki gruba geçer.

Sıra numarası bileti. Bir numara alıyorsun. Numaran çağrıldığında orada olmazsan, bir sonraki numara çağrılır. Arkada yeni bir bilet alabilirsin.

Kodlamadan önce karşılaştır

  1. Her birinde, sıradaki yerin ne zaman sabitlenir: sen sorduğunda mı yoksa şey boşta kaldığında mı?
  2. Gelmeyen birine ne olur ve ne kadar süre alır?
  3. Birisi onu alana kadar şey ne olur?
  4. Ortak kuralı kitap, masa veya et içermeyen tek bir cümleyle belirt.

Hedef

Mobil ekip küçük bir test telefonu laboratuvarı paylaşıyor. Mühendisler bir model talep eder; o modelden bir telefon boşta kaldığında onlara sunulur ve iki saat içinde laboratuvar uygulamasından talep etmeleri gerekir. Talep edilen bir telefon sekiz saatlik bir slot için rezerve edilir ve sonra otomatik olarak geri döner. Bugün uygulama "claim" butonuna ilk basana boş bir telefon veriyor ve insanlar butona basmak için scriptler yazmaya başladı.

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)
Senin sıran

loans(stock, events) yaz. stock, zaman 0'da boşta olan tüm (device_id, model)'leri listeler. events'ler, t dakikasına göre sıralanmış ("request", t, person, model) veya ("claim", t, person, model)'lerdir. Kurallar:

  1. Her modelin istek sırasına göre bir kuyruğu vardır. Eğer o kişi zaten o model için kuyrukta bekliyorsa veya o model için bir teklif tutuyorsa, istek görmezden gelinir.
  2. modelindeki sıradaki ilk kişiye ücretsiz bir telefon sunulur (sıradan çıkarlar). Eğer sırada kimse yoksa rafta bekler ve o model için daha sonra gelen bir istek onu hemen alır. Rafta birden fazla varsa, en küçük cihaz id'sini sun.
  3. o zamanında yapılan bir teklif t < o + 120 sırasında talep edilebilir. O kişi ve model için aktif bir teklifi olmayan bir talep görmezden gelinir.
  4. o + 120de sahiplenilmemiş bir teklif geçerliliğini yitirir ve telefon o anda tekrar boşalır (kural 2).
  5. A t zamanında bir kredi başlatır; telefon t + 480.
  6. tarihinde serbest kalır.
  7. Lapses ve returns due at or before an event's time, olay zamanından önce gerçekleşir; önce zaman sırasına, sonra device id sırasına göre dizilir.
Kredileri talep edildikleri sırayla (person, device_id, claim_time) olarak döndür.

Bu derste bir sorun mu fark ettin? Bildir · Bu ders hakkında soru sor

Bu alıştırma yakında açılacak

Bu dersi bitirince bu ders açılacak. Kursun tamamı ücretsiz, hesap gerekmiyor ve bu dersi hemen şimdi okuyabilirsin.