Job Sequencing Problem

Q: Apa kompleksitas waktu dari masalah penjadwalan pekerjaan?

Dengan disjoint set, kompleksitas waktunya adalah O(n log n) , didominasi oleh pengurutan, dan kompleksitas ruangnya O(n) . Memindai mundur dari setiap tenggat untuk mencari slot kosong membutuhkan O(n²) saat sebagian besar tenggat bernilai besar.

SedangGreedy Pengurutan

+10

Kamu mendapatkan n pekerjaan dalam bentuk dua array: pekerjaan i menghasilkan profit[i] jika selesai paling lambat pada waktu deadline[i]. Setiap pekerjaan membutuhkan satu satuan waktu, kamu menjalankan satu pekerjaan pada satu waktu mulai dari waktu 0, dan kamu boleh melewati pekerjaan apa pun. Pekerjaan dengan tenggat waktu 2 dapat dijalankan dari 0 hingga 1 atau dari 1 hingga 2.

Kembalikan total profit terbesar yang bisa kamu peroleh.

Fungsi

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

deadlineinteger-array: batas waktu setiap pekerjaan harus diselesaikan, dari 1 hingga n
profitinteger-array: penghasilan setiap pekerjaan; profit[i] sesuai dengan deadline[i]
Mengembalikaninteger: jumlah keuntungan total terbesar dari pekerjaan yang semuanya dapat diselesaikan sebelum tenggat waktunya

Batasan

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, dengan n adalah jumlah pekerjaan
1 ≤ profit[i] ≤ 10⁵
Array tidak diurutkan. Beberapa pekerjaan dapat memiliki tenggat waktu atau keuntungan yang sama.

Contoh

Input: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Output: 120
Penjelasan: Hanya satu dari dua pekerjaan dengan tenggat 1 yang muat, jadi jalankan pekerjaan yang bernilai 50. Pekerjaan yang bernilai 30 kemudian selesai tepat pada tenggatnya, yaitu 2, dan pekerjaan yang bernilai 40 selesai tepat pada tenggatnya, yaitu 3: 50 + 30 + 40 = 120.

Input: deadline = [1, 1, 1]profit = [5, 9, 7]
Output: 9
Penjelasan: Ketiga pekerjaan harus selesai paling lambat pada waktu 1, dan hanya satu pekerjaan yang muat sebelum waktu itu. Pekerjaan terbaik menghasilkan 9.

Pertanyaan lanjutan

Bagaimana jika pekerjaan i membutuhkan duration[i] satuan waktu, bukan satu? Apakah mengambil pekerjaan yang paling menguntungkan terlebih dahulu tetap menghasilkan total terbaik?

Solusi

Kamu memilih pekerjaan yang akan dipertahankan dan kapan menjalankannya. Satu aturan greedy menentukan keduanya: ambil pekerjaan dari yang paling menguntungkan, lalu tempatkan masing-masing di slot kosong paling akhir pada atau sebelum tenggatnya. Lewati pekerjaan jika tidak ada slot kosong. Disjoint set menemukan slot tersebut tanpa melewati slot yang sudah terisi.

Pendekatan greedy berdasarkan keuntungan, dengan mencari slot kosong

Intuisi

Bagi waktu menjadi slot: slot t berlangsung dari t-1 hingga t, pekerjaan dengan tenggat d dapat menggunakan slot 1 hingga d, dan tidak ada tenggat yang melebihi n. Memilih pekerjaan paling menguntungkan terlebih dahulu aman: jika semua slot yang dapat digunakan sudah terisi, menukarnya dengan pekerjaan di salah satu slot itu menghasilkan keuntungan setidaknya sama besar. Memilih slot paling akhir juga aman karena slot awal adalah satu-satunya slot yang dapat digunakan pekerjaan dengan tenggat pendek.

Biayanya berasal dari pemindaian. Jika setiap tenggat adalah n, pekerjaan ke-k melewati k-1 slot yang sudah terisi: sekitar n²/2, atau 12,5 juta langkah saat n = 5000.

Algoritma

Urutkan pekerjaan berdasarkan profit, dari yang terbesar, dan pertahankan setiap tenggat bersama profitnya.
Buat array taken dengan n + 1 flag, semuanya bernilai false.
Untuk setiap pekerjaan, turunkan t dari tenggatnya hingga 1 dan berhenti di slot pertama yang belum diambil.
Jika kamu menemukannya, tandai slot itu sudah diambil dan tambahkan profit pekerjaan ke total.
Kembalikan total.

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

Greedy berdasarkan profit dengan himpunan terpisah untuk slot yang tersedia

Intuisi

Pemindaian menelusuri slot yang sama dan sudah dipesan berulang kali. Disjoint set pada slot 0 hingga n melewati slot-slot tersebut: parent[t] = t selama slot t masih kosong, dan saat slot itu dipesan, nilainya diatur menjadi parent[t] = t-1, sehingga mengikuti pointer dari tenggat waktu akan membawa kita ke slot kosong terbaru. Jika mencapai slot 0, berarti tidak ada slot tersisa. Path halving membuat setiap slot yang kamu lewati menunjuk dua langkah ke depan, sehingga penelusuran berikutnya menjadi lebih singkat.

Pada contoh ketiga, pekerjaan bernilai 60 dan 50 memesan slot 2 dan 1. Pekerjaan bernilai 20 dengan tenggat waktu 2 mengikuti jalur dari 2 ke 1 lalu ke 0, sehingga dilewati.

Pengurutan membutuhkan O(n log n), dan dengan path halving, setiap pencarian membutuhkan O(log n) secara amortisasi, sehingga totalnya tetap O(n log n).

Algoritma

Urutkan pekerjaan berdasarkan profit, dari yang terbesar, dengan tetap menyertakan deadline masing-masing.
Tetapkan parent[t] = t untuk setiap slot t dari 0 hingga n.
Untuk setiap pekerjaan, mulai dari slot = deadline dan ikuti parent hingga parent[slot] == slot, sambil membagi dua jalur.
Jika slot > 0, tambahkan profit pekerjaan dan tetapkan parent[slot] = slot-1; jika tidak, lewati pekerjaan tersebut.
Kembalikan totalnya.

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

Jebakan dan kasus tepi

Menempatkan pekerjaan di slot kosong paling awal. Pada contoh ketiga, pekerjaan bernilai 60 akan menempati slot 1, dan pekerjaan bernilai 50 akan hilang: hasilnya 80, bukan 110.
Mengambil pekerjaan berdasarkan urutan tenggat waktu. Dengan tenggat waktu [1, 1] dan keuntungan [1, 100], pekerjaan berkeuntungan kecil mengambil satu-satunya slot, sehingga kamu memperoleh 1, bukan 100.
Mengatur ukuran array slot menjadi n, bukan n + 1. Tenggat waktu yang sama dengan n akan mengakses melewati batas akhir.
Mengurutkan keuntungan saja. Setiap tenggat waktu harus berpindah bersama keuntungannya.
Menulis langkah pencarian dengan rekursi. Rantai melalui ribuan slot yang sudah terisi dapat membuat stack overflow. Gunakan perulangan.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari masalah penjadwalan pekerjaan?

Dengan disjoint set, kompleksitas waktunya adalah O(n log n), didominasi oleh pengurutan, dan kompleksitas ruangnya O(n). Memindai mundur dari setiap tenggat untuk mencari slot kosong membutuhkan O(n²) saat sebagian besar tenggat bernilai besar.

Mengapa pendekatan greedy berhasil untuk penjadwalan pekerjaan?

Beberapa jadwal terbaik berisi pekerjaan yang paling menguntungkan. Jika pekerjaan itu tidak disertakan dan ada slot kosong sebelum tenggatnya, menambahkannya akan menghasilkan lebih banyak; jika semua slot tersebut sudah terisi, mengganti pekerjaan lain dengan pekerjaan itu menghasilkan setidaknya jumlah yang sama. Argumen ini berlaku berulang kali untuk pekerjaan yang tersisa.

Apakah masalah penjadwalan pekerjaan juga bisa diselesaikan menggunakan heap?

Ya. Urutkan pekerjaan berdasarkan tenggat waktu dan masukkan setiap keuntungan ke dalam min-heap. Setiap kali heap menampung lebih banyak pekerjaan daripada yang diizinkan oleh tenggat waktu saat ini, keluarkan keuntungan terkecil. Pada akhirnya, heap menampung kumpulan pekerjaan terbaik, dan jumlahnya adalah jawabannya, dalam O(n log n).

def jobSequencing(deadline, profit):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan