My first Magazine pemrograman-kompetitif-dasar | Page 70

6 Greedy
Gambar 6.12: Langkah 7: Memilih interval h13, 14i.
Gambar 6.13: Langkah 8: Sudah tidak ada pilihan tersedia. Langkah selesai.
Dengan melakukan proses tersebut, kita bisa mendapatkan 4 interval. Tidak ada cara lain
yang memberikan hasil lebih optimal. Implementasi dari algoritma tersebut dapat dilihat pada
Algoritma 26:
Algoritma 26 Penyelesaian activity selection.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function SOLVE A CTIVITY S ELECTION (a, N)
SORT B Y E ND T IME (a, N)
. Urutkan a secara menaik berdasarkan a[i].end
selectedCount ← 0
startTime ← 0
for i ← 1, N do
if (a[i].start ≥ startTime) then
selectedCount ← selectedCount + 1
startTime ← a[i].end
end if
end for
return selectedCount
end function
Mari kita analisis kompleksitas dari algoritma tersebut. Mengurutkan aktivitas berdasarkan
waktu berakhirnya dapat dilakukan dalam O(N log N). Setelah diurutkan, pemilihan aktivitas dapat
dilakukan dalam O(N). Maka, kompleksitas akhirnya adalah O(N log N).
6.5
Permasalahan pada Algoritma Greedy
Greedy choice memungkinkan kita untuk memilih suatu keputusan yang dijamin akan mengha-
silkan solusi optimal, tanpa peduli ke depannya seperti apa. Hal ini memberi kesan "rakus", yaitu
hanya mementingkan masalah yang sedang dihadapi dan selalu mengambil keputusan terbaik
saat ini. Inilah sebabnya teknik ini dinamakan greedy .
Karena sifatnya yang "rakus", ada persoalan-persoalan yang tidak dapat diselesaikan dengan
greedy . Perhatikan contoh soal berikut:
60