A Greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

Think of a Supermarket Sweep:

1. You have 60 seconds to grab as much value as possible.
2. You see a $500 TV and a $5 bag of chips.
3. You grab the TV immediately because it's the best choice right now.
4. You don't stop to calculate if grabbing 100 bags of chips would be better in the long run. You just take the big win!

---

The Greedy Choice Property

A global optimum can be arrived at by selecting a local optimum.

The Optimal Substructure

An optimal solution to the problem contains an optimal solution to subproblems.

Warning!

Greedy doesn't always work. For example, in the Coin Change problem, a greedy approach might fail if the coin denominations are unusual (e.g., $1, 3, 4$). Greedy would pick 4, then two 1s (3 coins). But two 3s (2 coins) is better!

---

In Fractional Knapsack, you can take "parts" of an item (like gold dust). This makes it a perfect candidate for Greedy.

javascript Standard
/**
 * Fractional Knapsack - O(n log n)
 */
function fractionalKnapsack(capacity, items) {
  // 1. Sort by value-to-weight ratio (Greedy Choice)
  items.sort((a, b) => (b.val / b.wt) - (a.val / a.wt));

  let totalValue = 0;
  for (let item of items) {
    if (capacity >= item.wt) {
      // Take the whole thing
      capacity -= item.wt;
      totalValue += item.val;
    } else {
      // Take a fraction
      totalValue += item.val * (capacity / item.wt);
      break; 
    }
  }
  return totalValue;
}

---

Top Techniques

• Sorting First: 90% of greedy problems start with sorting the input based on some criteria (End time, Value density, etc.).
• Interval Scheduling: Finding the maximum number of non-overlapping meetings. (Sort by End Time!).

Common Questions

• When does a Greedy algorithm fail?
• What is the difference between Greedy and Dynamic Programming? (Answer: Greedy never reconsiders choices; DP explores all paths and remembers results).
• Huffman Coding (Used in file compression). 💰