Greedy Algorithm selalu memilih opsi terbaik saat ini tanpa memikirkan dampak jangka panjang. Kadang ini menghasilkan solusi optimal, kadang tidak.

Kapan greedy bekerja? Jika masalah punya greedy-choice property — pilihan lokal terbaik selalu mengarah ke solusi global terbaik.

Contoh 1: Coin Change (greedy works)

// Kembalian minimum (denominasi: 1, 5, 10, 25)
function coinChange(amount) {
  const coins = [25, 10, 5, 1];
  const result = [];

  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }

  return result;
}

coinChange(41); // [25, 10, 5, 1] → 4 koin

Peringatan: Greedy untuk coin change tidak selalu optimal. Dengan denominasi [1, 3, 4], greedy untuk 6 = [4, 1, 1] (3 koin), tapi optimal = [3, 3] (2 koin). Gunakan DP untuk kasus umum.

Contoh 2: Activity Selection

// Pilih aktivitas terbanyak yang tidak overlap
function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a.end - b.end);

  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selected;
}

Greedy vs Dynamic Programming:

🎭 Analogi sehari-hari: Greedy = makan prasmanan dengan strategi "ambil yang paling enak dulu". Kadang ini optimal (kamu kenyang dengan makanan favorit). Kadang gak (lihat ada lobster di akhir, perut udah penuh). Greedy bagus untuk masalah yang lokal optimal = global optimal, tapi banyak masalah gak begitu.

💡 Cara cek apakah greedy works:

1. Buktikan secara matematik (susah)
2. Bandingkan dengan DP untuk test cases — kalau hasilnya sama, greedy bisa dipakai
3. Cari counterexample — kalau ketemu greedy gagal, jangan pakai

Standar: kalau buktinya ribet, pakai DP (lebih aman).

⚠️ Jebakan umum:

• Asumsi greedy works tanpa proof = solusi salah di edge case
• Coin Change non-canonical — denominasi seperti [1,3,4] greedy gagal (6 = greedy 4+1+1 = 3 koin, optimal 3+3 = 2 koin)
• Sort by attribute salah — Activity Selection wajib by end time, bukan start atau duration
• Greedy gak handle constraint kompleks — kadang butuh DP

🎯 Greedy biasanya works untuk:

• Activity selection / interval scheduling (sort by end)
• Huffman coding (selalu pilih 2 frequency terkecil)
• Dijkstra/Prim/Kruskal (selalu pilih edge terkecil)
• Fractional knapsack (sort by value/weight ratio)
• Coin change canonical (denominasi standar)

❌ Greedy GAGAL untuk:

• 0/1 Knapsack (harus DP)
• Coin Change non-canonical (harus DP)
• Longest path (greedy nyasar)

🧪 Tebakan cepat: Coin change [1, 3, 4] untuk 6. Greedy: 4+1+1 = 3 koin. Optimal (DP): 3+3 = 2 koin. Greedy salah. Selalu cek dulu.

TL;DR: Greedy = pilih lokal optimal di setiap langkah. Cepat dan simpel TAPI gak selalu optimal. Wajib ada greedy-choice property. Kalau ragu, pakai DP.