Rangkuman: Activity Selection Problem

1. Pengertian

Activity Selection Problem adalah masalah optimasi di mana kita diberikan serangkaian aktivitas, masing-masing dengan waktu mulai dan waktu selesai. Tujuan kita adalah memilih subset aktivitas terbesar yang saling kompatibel, artinya tidak ada dua aktivitas yang tumpang tindih (overlap).

Masalah ini adalah contoh klasik dari algoritma greedy karena solusi optimal global dapat dicapai dengan membuat pilihan optimal secara lokal pada setiap langkah.

2. Konsep Dasar & Pendekatan Greedy

Pendekatan greedy untuk masalah ini adalah dengan selalu memilih aktivitas yang memiliki waktu selesai (finish time) paling awal, di antara aktivitas yang tersisa dan kompatibel dengan aktivitas yang sudah dipilih.

Langkah-langkahnya:

1. Urutkan semua aktivitas berdasarkan waktu selesai (finish time) secara menaik.
2. Pilih aktivitas pertama yang selesai paling awal. Ini adalah aktivitas pertama yang masuk dalam solusi.
3. Untuk aktivitas selanjutnya, pilih aktivitas yang waktu mulai (start time) nya lebih besar atau sama dengan waktu selesai aktivitas terakhir yang sudah dipilih.
4. Ulangi langkah 3 sampai tidak ada lagi aktivitas yang bisa dipilih.

3. Contoh Ilustrasi

Misalkan kita punya aktivitas berikut (Start, Finish):

• A1: (1, 4)
• A2: (3, 5)
• A3: (0, 6)
• A4: (5, 7)
• A5: (3, 8)
• A6: (5, 9)

Koreksi Urutan Berdasarkan Finish Time:

1. A1: (1, 4)
2. A2: (3, 5)
3. A3: (0, 6)
4. A4: (5, 7)
5. A5: (3, 8)
6. A6: (5, 9)

Proses Pemilihan:

• Pilih A1 (1, 4). Waktu selesai terakhir = 4.
• Cari aktivitas yang start timenya >= 4. A4 (5, 7) adalah yang berikutnya. Pilih A4. Waktu selesai terakhir = 7.
• Cari aktivitas yang start timenya >= 7. Tidak ada.

Solusi Optimal: {A1, A4}

4. Pseudocode Algoritma

FUNCTION ActivitySelection(activities):
    SORT activities by their finish time in non-decreasing order

    solution = []
    solution.ADD(activities[0]) // Tambahkan aktivitas pertama yang selesai paling awal
    last_finish_time = activities[0].finish_time

    FOR i FROM 1 TO activities.LENGTH - 1:
        current_activity = activities[i]
        IF current_activity.start_time >= last_finish_time:
            solution.ADD(current_activity)
            last_finish_time = current_activity.finish_time

    RETURN solution
                    

5. Kompleksitas Waktu & Ruang

• Kompleksitas Waktu:
  • Pengurutan aktivitas: $O(N \log N)$, di mana N adalah jumlah aktivitas.
  • Pemilihan aktivitas: $O(N)$ (sekali iterasi setelah pengurutan).
  • Total: $O(N \log N)$
• Kompleksitas Ruang: $O(N)$ untuk menyimpan aktivitas dan solusi.

6. Aplikasi

• Penjadwalan rapat atau acara yang tidak boleh tumpang tindih.
• Alokasi sumber daya terbatas (misalnya, ruang kelas, proyektor) untuk beberapa proyek.
• Manajemen tugas dalam sistem operasi.