Memahami Activity Selection Problem

Apa itu Activity Selection Problem?

Activity Selection Problem adalah masalah optimisasi klasik yang menggunakan pendekatan greedyuntuk memilih jumlah maksimum aktivitas yang tidak saling tumpang tindih (non-overlapping) dari sebuah himpunan aktivitas. Setiap aktivitas memiliki waktu mulai dan selesai, dan tujuannya adalah memilih sebanyak mungkin aktivitas yang dapat dilakukan secara berurutan pada satu sumber daya (misalnya, satu ruangan atau satu orang).

Masalah ini memiliki aplikasi dalam berbagai bidang, seperti:

• Penjadwalan: Mengatur rapat atau acara dalam satu ruangan
• Manajemen tugas: Memilih tugas yang dapat diselesaikan dalam waktu tertentu
• Sistem operasi: Penjadwalan proses dalam CPU
• Jaringan: Pengalokasian sumber daya jaringan untuk transmisi data

Cara Kerja Activity Selection Problem

Algoritma greedy untuk Activity Selection Problem memilih aktivitas berdasarkan waktu selesai yang paling awal. Berikut langkah-langkahnya:

1. Urutkan aktivitas:
   • Urutkan semua aktivitas berdasarkan waktu selesai (finish time) secara ascending
2. Pilih aktivitas:
   • Pilih aktivitas pertama (dengan waktu selesai paling awal)
   • Tandai waktu selesai aktivitas ini sebagai batas waktu terakhir
3. Iterasi aktivitas berikutnya:
   • Untuk setiap aktivitas berikutnya dalam daftar yang sudah diurutkan:
   • Jika waktu mulai aktivitas lebih besar atau sama dengan batas waktu terakhir, pilih aktivitas tersebut
   • Perbarui batas waktu terakhir dengan waktu selesai aktivitas yang dipilih

Pendekatan ini menjamin bahwa kita mendapatkan jumlah maksimum aktivitas yang kompatibel (tidak tumpang tindih).

Contoh Permasalahan

Misalkan kita memiliki aktivitas berikut dengan waktu mulai dan selesai:

Aktivitas yang dipilih: A1, A3, A5 (ditandai hijau)

Langkah-langkah solusi:

1. Urutkan berdasarkan waktu selesai: A1(4), A2(5), A3(7), A4(8), A5(9)
2. Pilih A1 (selesai jam 4)
3. Lewati A2 dan A4 (waktu mulai kurang dari 4)
4. Pilih A3 (mulai jam 5, selesai jam 7)
5. Pilih A5 (mulai jam 8, selesai jam 9)

Implementasi Kode (Python)

Berikut implementasi Activity Selection Problem menggunakan Python:

def activity_selection(start, finish):
    # Urutkan aktivitas berdasarkan waktu selesai
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    result = []
    last_finish_time = -1
    
    # Pilih aktivitas
    for s, f in activities:
        if s >= last_finish_time:
            result.append((s, f))
            last_finish_time = f
    
    return result

# Contoh penggunaan
start = [1, 3, 5, 3, 8]
finish = [4, 5, 7, 8, 9]
selected_activities = activity_selection(start, finish)
print("Aktivitas yang dipilih:", selected_activities)

Output akan menampilkan daftar aktivitas yang dipilih berdasarkan waktu mulai dan selesai.

Implementasi Kode (JavaScript)

Berikut implementasi yang sama dalam JavaScript:

function activitySelection(start, finish) {
    // Gabungkan start dan finish ke dalam array aktivitas
    const activities = start.map((s, i) => ({ start: s, finish: finish[i] }));
    
    // Urutkan berdasarkan waktu selesai
    activities.sort((a, b) => a.finish - b.finish);
    
    const result = [];
    let lastFinishTime = -1;
    
    // Pilih aktivitas
    for (let activity of activities) {
        if (activity.start >= lastFinishTime) {
            result.push(activity);
            lastFinishTime = activity.finish;
        }
    }
    
    return result;
}

// Contoh penggunaan
const start = [1, 3, 5, 3, 8];
const finish = [4, 5, 7, 8, 9];
const selectedActivities = activitySelection(start, finish);
console.log("Aktivitas yang dipilih:", selectedActivities);

Kompleksitas dan Optimasi

Kompleksitas Waktu:

Kompleksitas waktu adalah O(n log n) karena langkah pengurutan mendominasi proses, di mana n adalah jumlah aktivitas.

Kompleksitas Ruang:

Kompleksitas ruang adalah O(n) untuk menyimpan daftar aktivitas yang diurutkan dan hasilnya.

Optimasi:

• Pre-sorting: Jika data sudah diurutkan, kompleksitas waktu menjadi O(n)
• Parallel sorting:Menggunakan algoritma pengurutan paralel untuk data besar
• In-place sorting: Mengurangi penggunaan memori tambahan selama pengurutan

Kelebihan dan Kekurangan

Kelebihan Activity Selection Problem:

• Sederhana: Algoritma greedy mudah diimplementasikan dan dipahami
• Efisien: Memberikan solusi optimal dengan kompleksitas rendah
• Fleksibel: Dapat dimodifikasi untuk kriteria pemilihan lain

Kekurangan Activity Selection Problem:

• Asumsi tidak tumpang tindih:Tidak cocok untuk aktivitas dengan overlap parsial
• Data harus diurutkan:Membutuhkan langkah pengurutan awal
• Keterbatasan kriteria:Hanya optimal untuk pemilihan berdasarkan waktu selesai

Kesimpulan

Activity Selection Problem adalah contoh klasik dari penggunaan algoritma greedy untuk menyelesaikan masalah penjadwalan. Dengan pendekatan sederhana berdasarkan waktu selesai, algoritma ini menjamin solusi optimal untuk memilih aktivitas maksimum yang tidak tumpang tindih. Meskipun memiliki keterbatasan, algoritma ini sangat efisien dan sering digunakan dalam aplikasi penjadwalan dan optimisasi sumber daya.