Job Sequencing Problem

+10

Sana iki dizi olarak n iş veriliyor: i. iş, deadline[i] zamanına kadar tamamlanırsa profit[i] kazandırır. Her iş bir zaman birimi sürer, aynı anda bir iş yaparsın ve 0 zamanında başlarsın; istediğin işleri atlayabilirsin. Son teslim tarihi 2 olan bir iş, 0 ile 1 arasında veya 1 ile 2 arasında yapılabilir.

Elde edebileceğin en yüksek toplam kârı döndür.

Fonksiyon

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: her işin tamamlanması gereken zaman, 1 ile n arasında
profitinteger-array: her işin ne kadar kazandırdığı; profit[i], deadline[i] öğesine aittir
Döndürürinteger: Son teslim tarihlerine kadar tamamlanabilecek işlerin en yüksek toplam kârı

Kısıtlar

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, burada n iş sayısıdır
1 ≤ profit[i] ≤ 10⁵
Diziler sıralı değildir. Birden fazla işin son teslim tarihi veya kârı aynı olabilir.

Örnekler

Girdi: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Çıktı: 120
Açıklama: Son tarihi 1 olan iki işten yalnızca biri sığar, bu yüzden değeri 50 olanı çalıştır. Değeri 30 olan iş daha sonra son tarihi 2'de, değeri 40 olan iş ise son tarihi 3'te tamamlanır: 50 + 30 + 40 = 120.

Girdi: deadline = [1, 1, 1]profit = [5, 9, 7]
Çıktı: 9
Açıklama: Üç işin de 1. zamana kadar tamamlanması gerekiyor ve bu süreden önce yalnızca bir iş sığıyor. Bunların en iyisi 9 kazandırıyor.

Ek soru

Ya iş i, bir birim zaman yerine duration[i] birim zaman alıyorsa? Önce en kârlı işi yapmak yine de en yüksek toplam kazancı sağlar mı?

Çözüm

Hangi işleri tutacağınıza ve ne zaman çalıştıracağınıza siz karar verirsiniz. Tek bir açgözlü kural her ikisini de belirler: işleri en kârlı olandan başlayarak alın ve her birini son teslim tarihinden önce veya o tarihteki en geç boş slota yerleştirin; boş slot yoksa işi atlayın. Ayrık kümeler, dolu slotları tek tek geçmeden bu slotu bulur.

Kâra göre açgözlü seçim, boş bir zaman aralığı arayarak

Sezgi

Zamanı zaman dilimlerine böl: t dilimi t-1 ile t arasında sürer, son teslim tarihi d olan bir iş 1 ile d arasındaki dilimleri kullanabilir ve hiçbir son teslim tarihi n'i aşmaz. En kârlı işi önce almak güvenlidir: kullanabileceği her dilim doluysa, onu bu dilimlerden birindeki işle değiştirmek en az aynı kazancı sağlar. En geç dilime yerleştirmek güvenlidir; çünkü kısa son teslim tarihli işlerin kullanabileceği tek dilimler erken dilimlerdir.

Maliyet taramadır. Her işin son teslim tarihi n olduğunda, k. iş dolu k-1 dilimin üzerinden geçer: yaklaşık n²/2, yani n = 5000 için 12,5 milyon adım.

Algoritma

İşleri kâra göre büyükten küçüğe sıralayın; her işin son teslim tarihini kârıyla birlikte tutun.
Tüm değerleri false olan n + 1 bayraklı bir taken dizisi oluşturun.
Her iş için t değerini son teslim tarihinden başlayarak 1'e kadar azaltın ve alınmamış ilk yuvada durun.
Bir yuva bulduysanız, onu alınmış olarak işaretleyin ve işin kârını total değerine ekleyin.
total değerini döndürün.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Kârı temel alan açgözlü yaklaşım ve ayrık serbest zaman aralıkları kümesi

Sezgi

Tarama, aynı ayrılmış zaman dilimlerinin üzerinden tekrar tekrar geçer. 0 ile n arasındaki zaman dilimleri üzerinde ayrık kümeler kullanmak bunları atlar: parent[t] = t iken t zaman dilimi boştur ve bu zaman dilimini ayırmak parent[t] = t-1 atamasını yapar; böylece bir son tarihten işaretçileri izlemek, en son boş zaman dilimine ulaşır. 0. zaman dilimine ulaşmak, geriye hiçbir şey kalmadığı anlamına gelir. Yol yarılama, geçtiğiniz her zaman dilimini iki adım ilerideki zaman dilimine yönlendirir; böylece sonraki geçişler kısalır.

Üçüncü örnekte, değeri 60 ve 50 olan işler 2. ve 1. zaman dilimlerini ayırır. Değeri 20 olan, son tarihi 2 olan iş, 2'den 1'e, oradan da 0'a gider ve atlanır.

Sıralama O(n log n) maliyetindedir ve yol yarılama ile her arama amortize edilmiş olarak O(log n) maliyetindedir; dolayısıyla toplam maliyet O(n log n) olarak kalır.

Algoritma

İşleri, son tarihlerini kârlarıyla birlikte koruyarak, kârı en yüksek olandan başlayacak şekilde sırala.
0'dan n'ye kadar her t yuvası için parent[t] = t olarak ayarla.
Her iş için slot = deadline ile başla ve ilerlerken yolu yarıya indirerek parent[slot] == slot olana kadar parent değerlerini takip et.
slot > 0 ise işin kârını ekle ve parent[slot] = slot-1 olarak ayarla; aksi takdirde işi atla.
Toplamı döndür.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Tuzaklar ve uç durumlar

Bir işi en erken boş slota yerleştirmek. Üçüncü örnekte değeri 60 olan iş 1. slota yerleşir ve değeri 50 olan iş kaybedilir: 110 yerine 80 elde edilir.
İşleri son teslim tarihlerine göre sıralamak. Son teslim tarihleri [1, 1] ve kârlar [1, 100] olduğunda, düşük kârlı iş tek slotu alır ve 100 yerine 1 kazanırsın.
Slot dizisinin boyutunu n + 1 yerine n olarak belirlemek. Bu durumda n'ye eşit bir son teslim tarihi, dizinin sonunu aşan bir konumdan okuma yapar.
Kârları tek başlarına sıralamak. Her son teslim tarihi, kârıyla birlikte hareket etmelidir.
Bulma adımını özyinelemeyle yazmak. Binlerce dolu slot boyunca ilerleyen bir zincir yığını taşırabilir; döngü kullan.

Sıkça sorulan sorular3

İş sıralama probleminin zaman karmaşıklığı nedir?

Ayrık kümeyle zaman karmaşıklığı, sıralamanın baskın olduğu O(n log n); alan karmaşıklığı ise O(n) olur. Boş bir yeri bulmak için her son teslim tarihinden geriye doğru taramak, son teslim tarihlerinin çoğu büyük olduğunda O(n²) maliyetlidir.

İş sıralaması için açgözlü yaklaşım neden işe yarar?

En iyi çizelgelerden bazıları en kârlı işi içerir. Bu iş dışarıda bırakılmışsa ve son teslim tarihinden önceki bir zaman aralığı boşsa, onu eklemek daha fazla kazanç sağlar; bu tür tüm zaman aralıkları doluysa, başka bir işi onunla değiştirmek en az aynı kazancı sağlar. Geriye kalan işler için de aynı akıl yürütme tekrarlanır.

İş sıralama problemi bunun yerine bir yığınla çözülebilir mi?

Evet. İşleri son teslim tarihlerine göre sırala ve her kârı bir min-heap'e ekle. Yığın, mevcut son teslim tarihinin izin verdiğinden daha fazla iş içerdiğinde en küçük kârı çıkar. Sonunda yığın en iyi iş kümesini tutar ve bu kümedeki kârların toplamı, O(n log n) içinde yanıtı verir.

def jobSequencing(deadline, profit):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Beklenen Çıktı