Etkinlik Seçimi

#Nasıl çalışır?

Açgözlü (greedy) bir algoritma her adımda o an en iyi görünen seçimi yapar ve bir daha geri dönmez. Bazı problemlerde bu yerel seçimler küresel en iyi çözümü verir; bazılarında vermez. Hangisi olduğunu kanıtlamak açgözlü algoritmaların asıl zorluğudur.

Etkinlik seçimi probleminde başlangıç ve bitiş zamanları verilen etkinliklerden, birbiriyle çakışmayan en fazla sayıda etkinlik seçilmek istenir; örneğin tek bir toplantı salonu için.

Doğru açgözlü kural: en erken biten etkinliği seç, onunla çakışanları ele, kalanlar için tekrarla. Erken biten etkinlik salonu en kısa sürede boşaltır ve geriye en çok zaman bırakır. "En erken başlayan" ya da "en kısa süren" gibi kurallar ise yanlış cevap verebilir; derste bunu görebilirsin.

#Kendin dene

#Adım adım

1. 01Etkinlikleri bitiş zamanına göre sırala.
2. 02İlk etkinliği seç; son bitiş zamanını onun bitişi yap.
3. 03Sıradaki etkinlik son bitişten sonra (ya da tam o anda) başlıyorsa seç ve son bitişi güncelle.
4. 04Aksi halde atla; liste bitene kadar devam et.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

# (start, end) of each activity; numbered 1..11 in this order.
ACTIVITIES = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]


def select(activities: list) -> list:
    """Most activities that don't overlap: earliest finish first."""
    order = sorted(range(len(activities)), key=lambda i: activities[i][1])
    chosen, last_end = [], float("-inf")
    for i in order:
        start, end = activities[i]
        if start >= last_end:  # doesn't overlap the last one taken
            chosen.append(i + 1)
            last_end = end
    return chosen


chosen = select(ACTIVITIES)
print(len(chosen))
print(" ".join(map(str, chosen)))

#Karmaşıklık

Süreyi sıralama belirler; tarama tek geçiştir. Kuralın doğruluğu bir değiştirme argümanıyla kanıtlanır: herhangi bir en iyi çözümün ilk etkinliği, en erken biten etkinlikle değiştirilebilir ve çözüm hâlâ geçerli kalır.

#Ne zaman kullanılır?

Toplantı odası ve kaynak planlama, CPU'da iş zamanlama, reklam yayın aralıkları ve tek kaynağın paylaşıldığı her türlü zamanlama problemi. Etkinliklerin farklı değerleri varsa (ağırlıklı aralık seçimi) açgözlü yöntem yetmez, DP gerekir.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.