İçeriğe geç

Aralık zamanlama

Ders 2 / 5 · 5 dk

Aralık zamanlama

Adım 1/10

Tek oda için beş rezervasyon. Hiçbir ikisi çakışmadan olabildiğince çoğunu al.

Fikir

Tek bir odada, birbiriyle çakışmayan olabildiğince çok iş yapmak istiyorsun. Bitiş zamanına göre sırala, sonra listeyi dolaş ve son aldığın işin bitişinde ya da sonrasında başlayan her işi al.

Önemli olan tek şey erken bitmek; çünkü en erken biten iş, geri kalan her şey için günün en büyük dilimini bırakır. Süre de başlangıç zamanı da yalnızca dikkat dağıtır.

Gerçek hayattan örnek

Bir post-prodüksiyon şirketindeki tek kurgu odasını düşün. Bugün altı müşteri odayı istiyor; planlayıcı, odayı en erken boşaltan rezervasyonu kabul eder. Böylece en çok müşteriye hizmet verilir; ne ilk soran öne geçer ne de en uzun iş.

Kod

Sıra sende

Adımları doğru sıraya koy.

  1. İş o zamanda ya da sonra başlıyorsa kabul et ve odanın boşalma zamanını işin bitişine taşı
  2. Bütün işleri bitiş zamanına göre sırala
  3. Değilse işi atla, çünkü zaten rezerve edilmiş olanla çakışıyor
  4. Odanın eksi sonsuzdan beri boş olduğunu varsayarak başla
  5. Sıradaki işin başlangıcını boşalma zamanıyla karşılaştır

Mini quiz

1 / 3

Aralık zamanlamada (interval scheduling) greedy (açgözlü) yaklaşımı hangi anahtar doğru kılar?