Etkinlik Seçimi

Açgözlü Algoritmalar O(n log n) O(1)

Her zaman en erken biteni alarak çakışmayan en fazla sayıda etkinliği seçer.

01234567891011

1–2

3–4

0–6

5–7

8–9

5–9

6–10

8–11

Bitiş zamanına göre sıralı — çizgi son bitişi gösterir.

1/20

Etkinlikler bitiş zamanına göre sıralandı — en erken biten önce.

DeğişmezEn erken biteni almak geri kalana en çok yeri bırakır — bu yüzden açgözlü seçim optimalden hiç kötü değildir.

değerlendiriliyorseçildireddedildi

activity-selection.c

/* activities sorted by finish time */
void activitySelect(int start[], int finish[], int n) {
    int lastFinish = finish[0];
    printf("select 0\n");
    for (int i = 1; i < n; i++) {
        if (start[i] >= lastFinish) {
            printf("select %d\n", i);
            lastFinish = finish[i];
        }
    }
}

Etkinlik Seçimi nasıl çalışır?

Bitiş zamanına göre sırala ve her zaman seni en erken serbest bırakan etkinliği al. En erken biten her zaman bir optimal çözüme takas edilebilir; açgözlü seçim güvenlidir.

Ne zaman kullanılır?

Tek kaynakta aralık planlama: toplantı odaları, makineler, CPU zaman dilimleri.