Activity Selection Problem

Q: Etkinlik seçimi probleminin zaman karmaşıklığı nedir?

Bitiş zamanına göre sıralama O(n log n) maliyetindedir ve ardından gelen açgözlü geçiş O(n) maliyetindedir; bu nedenle sıralama baskın maliyettir. Etkinlikler zaten bitiş zamanına göre sıralıysa, yalnızca geçiş işlemi bunu O(n) zamanda ve O(1) ek alanla çözer.

Q: N toplantının tek odada yapılması problemi nedir?

Toplantılarla anlatılan aynı problem: bir oda, N toplantı ve bir toplantı ancak önceki toplantı bittikten sonra başlayabilir. Toplantıları bitiş zamanına göre sırala ve alınan son toplantı bittikten sonra başlayan her toplantıyı al. Toplantıları listelemek için aldığın her toplantının indeksini kaydet; bitiş zamanları eşitse daha küçük indeksi tercih et.

KolayAçgözlü Sıralama

+10

i etkinliği, start[i] zamanında başlar ve finish[i] zamanında biter. Bir kişi aynı anda yalnızca bir etkinlik yapabilir ve sonraki etkinlik, önceki etkinlik bittikten kesinlikle daha sonra başlamalıdır: başka bir etkinliğin bittiği tam zamanda başlayan bir etkinlik, onu takip edemez.

Bir kişinin yapabileceği en fazla etkinlik sayısını döndürün.

Fonksiyon

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: her etkinliğin başlangıç zamanı
finishinteger-array: her etkinliğin bitiş zamanı; finish[i], start[i]'ye aittir
Döndürürinteger: bir kişinin art arda yapabileceği en fazla etkinlik

Kısıtlar

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Bir etkinlik aynı anda başlayıp bitebilir. Diziler sıralı değildir.

Örnekler

Girdi: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Çıktı: 4
Açıklama: 10'dan 13'e, 14'ten 19'a, 21'den 22'ye ve 25'ten 30'a yapmak 4 verir. Beş mümkün değil: 10'dan 13'e aralığı 12'den 16'ya aralığıyla, 21'den 22'ye aralığı ise 20'den 24'e aralığıyla çakışıyor.

Girdi: start = [1, 5, 9]finish = [5, 9, 12]
Çıktı: 2
Açıklama: 5'ten 9'a olan etkinlik, ilk etkinliğin tam bittiği anda başlıyor; bu yüzden onun ardından gelemez. 1'den 5'e ve ardından 9'dan 12'ye olan etkinlikleri yapmak işe yarar, dolayısıyla yanıt 2.

Girdi: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Çıktı: 3
Açıklama: 0'dan 100'e kadar olan etkinlik diğerlerinin tümüyle çakışıyor. Bunu dışarıda bıraktığımızda, 2'den 4'e, 5'ten 7'ye ve 8'den 10'a kadar olanlar art arda sıralanıyor: 3.

Ek soru

Artık iki kişi paralel olarak çalışıyor ve her biri aynı anda bir etkinlik yapıyor. Birlikte kaç etkinlik yapabilirler ve her birini hangi kişi üstlenmeli?

Çözüm

Etkinliklerin her alt kümesini denemek üstel zaman alır. Bunun yerine, tek bir açgözlü kural sorunu çözer: Hâlâ sığan etkinlikler arasından daima en erken biteni yap. Bitiş zamanına göre sıralama, bu kuralı tek geçişlik bir işleme dönüştürür.

En erken biteni tekrar tekrar seç

Doğru, ama en büyük testlerde bitmiyor

Sezgi

En erken biten etkinlik, en az diğer seçeneklerden herhangi biri kadar iyi bir ilk seçimdir. Seni daha geç serbest bırakmaz; dolayısıyla başka bir ilk seçimin ardından gelebilecek her şey bunun ardından da gelebilir ve bunu seçmek etkinlik sayısını korur. Bu seçimden sonra problem, bitişinin ardından başlayan etkinlikler için tekrarlanır.

İlk örnekte önce 10'dan 13'e kadar olanı, sonra 14'ten 19'a kadar olanı, ardından 21'den 22'ye kadar olanı ve son olarak 25'ten 30'a kadar olanı seçersin: dört etkinlik.

Her seçimde n etkinliğin tamamı taranır; dolayısıyla maliyet, yanıtın n katıdır. 5000 etkinliğin tümü art arda sığdığında bu, 25 milyon kontrol demektir.

Algoritma

Her başlangıcın altına count = 0 ve lastFinish = -1 değerlerini ayarlayın.
Tüm etkinlikleri tarayarak start[i] > lastFinish koşulunu sağlayan ve en erken biten etkinliği bulun.
Böyle bir etkinlik yoksa count değerini döndürün.
Aksi takdirde count değerini 1 artırın, lastFinish değerini bu etkinliğin bitiş zamanına ayarlayın ve yeniden tarayın.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Bitiş zamanına göre sırala ve açgözlü bir şekilde seç

Sezgi

Bitiş zamanına göre bir kez sıraladığında, etkinliklerle yukarıdaki taramaların onları aradığı sırada karşılaşırsın. Sıralanmış listeyi, aldığın son etkinliğin bitiş zamanı olan lastFinish değerini tutarak dolaş. start[i] > lastFinish koşulunu sağlayan bir etkinlik, hâlâ sığan ve en erken biten etkinliktir; bu yüzden onu al. Diğer tüm etkinlikler son seçiminle çakışır, dolayısıyla onları atlamanın bir maliyeti yoktur.

Sıralandığında ilk örnek 10'dan 13'e, 12'den 16'ya, 14'ten 19'a, 21'den 22'ye, 20'den 24'e ve 25'ten 30'a şeklindedir. İlkini, üçüncüsünü, dördüncüsünü ve altıncısını alırsın: 12, 13'ten sonra değildir ve 20, 22'den sonra değildir.

Bitiş zamanlarının eşit olması için bir kurala gerek yoktur. t zamanında biten bir etkinliği aldığında, aynı zamanda biten diğer tüm etkinlikler t anında veya daha önce başlar ve atlanır.

Algoritma

Etkinlikleri finish değerine göre sıralayın; her başlangıcı kendi bitişiyle birlikte taşıyın.
count = 0 ve lastFinish = -1 değerlerini ayarlayın.
Bu sıradaki her etkinlik için, start[i] > lastFinish ise count değerini 1 artırın ve lastFinish = finish[i] olarak ayarlayın.
count değerini döndürün.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Tuzaklar ve uç durumlar

Başlangıç zamanına göre sıralama. Üçüncü örnekte 0 ile 100 arasındaki etkinlik ilk başlar ve diğer üçünü engeller.
Önce en kısa etkinliği seçme. 1 ile 5, 5 ile 6 ve 6 ile 10 arasındaki etkinliklerde en kısa olan 5 ile 6 arasındakidir; bu etkinlik diğer ikisiyle çakışır. 1 ile 5 ve 6 ile 10 arasındaki etkinliklerin toplamı 2 eder.
> yerine ≥ ile karşılaştırma yapma. İkinci örnekte bu, 2 yerine 3 döndürür.
Yalnızca finish değerini sıralama. Her başlangıç kendi bitişiyle birlikte hareket etmelidir; yoksa başlangıçlar yanlış etkinliklerle eşleşir.
lastFinish değerini 0 olarak başlatma. Bu durumda 0 ile 1 arasındaki tek etkinlik atlanır, çünkü 0 > 0 yanlıştır.

Sıkça sorulan sorular3

Etkinlik seçimi probleminin zaman karmaşıklığı nedir?

Bitiş zamanına göre sıralama O(n log n) maliyetindedir ve ardından gelen açgözlü geçiş O(n) maliyetindedir; bu nedenle sıralama baskın maliyettir. Etkinlikler zaten bitiş zamanına göre sıralıysa, yalnızca geçiş işlemi bunu O(n) zamanda ve O(1) ek alanla çözer.

N toplantının tek odada yapılması problemi nedir?

Toplantılarla anlatılan aynı problem: bir oda, N toplantı ve bir toplantı ancak önceki toplantı bittikten sonra başlayabilir. Toplantıları bitiş zamanına göre sırala ve alınan son toplantı bittikten sonra başlayan her toplantıyı al. Toplantıları listelemek için aldığın her toplantının indeksini kaydet; bitiş zamanları eşitse daha küçük indeksi tercih et.

Etkinlik seçimi problemi dinamik programlama mıdır?

Olabilir, ancak olmak zorunda değildir. Bitiş zamanına göre sıralanmış etkinliklerden oluşan ve her biriyle biten en fazla sayıda etkinliği tutan bir tablo, yanıtı O(n²) sürede verir. Açgözlü seçim her zaman güvenlidir, bu nedenle tek geçiş yeterlidir. Etkinliklerin değerleri olduğunda ve toplam değerlerini en üst düzeye çıkardığınızda tablo doğru araç hâline gelir.

def maxActivities(start, finish):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Beklenen Çıktı