Greedy Theory & Examples

The Greedy Paradigm

Welcome to the Greedy paradigm, an algorithmic strategy that builds up a solution piece by piece, always choosing the option that looks best at the moment. A greedy algorithm makes a locally optimal choice at each stage with the hope of finding a global optimum.

---

1. The Core Idea: The Locally Optimal Choice

The essence of a greedy algorithm is to make the best possible choice at each step without reconsidering past choices. It's like climbing a hill by always taking the steepest path upwards. While this approach doesn't work for all problems, it can be surprisingly effective and efficient for many.

---

2. When Does Greedy Work? The Greedy Choice Property

Greedy algorithms work for problems that have the Greedy Choice Property. This means that a globally optimal solution can be arrived at by making a sequence of locally optimal choices.

Proving that a problem has this property is the key to designing a correct greedy algorithm.

---

3. Classic Examples

Many famous algorithms use a greedy approach.

• Dijkstra's Algorithm: At each step, it greedily selects the unvisited vertex with the smallest known distance from the source.

• Prim's and Kruskal's Algorithms: Both are greedy algorithms for finding a Minimum Spanning Tree. Prim's greedily adds the cheapest edge to the growing tree, while Kruskal's greedily adds the cheapest edge that doesn't form a cycle.

• Interval Scheduling: Given a set of intervals, find the maximum number of non-overlapping intervals.

  • Greedy Strategy: Sort the intervals by their finishing times. Pick the first interval, then repeatedly pick the next interval that starts after the last selected interval finishes.

  function maxNonOverlappingIntervals(intervals) {
    // Sort intervals by their end times
    intervals.sort((a, b) => a.end - b.end);
  
    const result = [];
    let lastEndTime = -Infinity;
  
    for (const interval of intervals) {
      if (interval.start >= lastEndTime) {
        result.push(interval);
        lastEndTime = interval.end;
      }
    }
    return result;
  }
  

• Huffman Coding: A greedy algorithm used for lossless data compression. It builds an optimal prefix code tree by repeatedly merging the two least frequent characters.

---

4. Proving Correctness

To be sure a greedy algorithm is correct, you often need to prove it. A common technique is an "exchange argument," where you assume there is a better solution and then show that your greedy choice is at least as good as, if not better than, the choice made by the supposed better solution.

---

Key Takeaway: Greedy algorithms make locally optimal choices at each step to find a global optimum. They are simple and efficient but only work for problems with the Greedy Choice Property. Always be sure to convince yourself that the greedy choice is the right one before using it.