İş Sıralama

Açgözlü Algoritmalar O(n²) O(n)

Son teslim tarihli birim işleri en yüksek kâr için planlar: her işi (en kârlı önce) son teslim tarihinden önceki en geç boş saate açgözlüce yerleştirir.

Ad≤2+100

Cd≤2+27

Dd≤1+25

Bd≤1+19

Ed≤3+15

saat 1

saat 2

saat 3

Kâra göre sıralı — her iş en geç boş saati kapar.toplam0

1/17

İşler kâra göre sıralandı — en kârlı önce.

DeğişmezHer iş son tarihinden önceki en geç boş saate yerleşir; bu, gelecek işler için erken saatleri açık tutar.

değerlendiriliyorseçildireddedildi

job-sequencing.c

/* jobs sorted by profit (desc) */
int jobSequence(int dl[], int p[], int n, int maxD) {
    int slot[maxD + 1];
    for (int t = 1; t <= maxD; t++)
        slot[t] = -1;                /* all hours free */
 
    int total = 0;
    for (int i = 0; i < n; i++) {
        for (int t = dl[i]; t >= 1; t--) {
            if (slot[t] == -1) {
                slot[t] = i;         /* latest free hour */
                total += p[i];
                break;
            }
        }
    }
    return total;
}

İş Sıralama nasıl çalışır?

Önce en yüksek kâr; her işi son teslim tarihinden önceki en geç boş saate koy. Geç planlamak, erken saatleri gelebilecek daha sıkışık işlere açık tutar.

Ne zaman kullanılır?

Teslim tarihli ve kâr/cezalı birim işler — zamanında biteni en çoklamak.