Greedy Algorithms: Concepts and Applications

Greedy algorithms are a class of algorithms that make the locally optimal choice at each step with the hope of finding the global optimum. They are often used for optimization problems where a sequence of choices leads to an optimal solution.

---

How Greedy Algorithms Work

A greedy algorithm follows this simple strategy:

1. Make the best choice at the current step.
2. Move to the next step without revisiting previous decisions.
3. Repeat until the problem is solved.

---

Characteristics of Greedy Algorithms

• Greedy Choice Property: A global optimum can be arrived at by choosing the local optimum.
• Optimal Substructure: A problem has an optimal substructure if an optimal solution can be built from optimal solutions of its subproblems.

Not all problems have these properties. If they do, a greedy algorithm can be very efficient.

---

Example: Activity Selection

Given n activities with start and end times, select the maximum number of activities that don't overlap.

import java.util.*;

class Activity {
  int start, end;

  Activity(int start, int end) {
    this.start = start;
    this.end = end;
  }
}

public class GreedyActivitySelector {
  public static void main(String[] args) {
    List<Activity> activities = List.of(
      new Activity(1, 3),
      new Activity(2, 5),
      new Activity(4, 7),
      new Activity(6, 9)
    );

    activities.sort(Comparator.comparingInt(a -> a.end));

    int lastEnd = 0;
    for (Activity a : activities) {
      if (a.start >= lastEnd) {
        System.out.println("Selected: " + a.start + "-" + a.end);
        lastEnd = a.end;
      }
    }
  }
}

This is a classic example of greedy algorithm success.

---

Common Greedy Algorithm Problems

• Activity Selection Problem
• Fractional Knapsack Problem
• Huffman Encoding
• Prim’s and Kruskal’s algorithms (Minimum Spanning Tree)
• Dijkstra’s algorithm (Shortest Path)

---

When Greedy Fails

Greedy algorithms do not always produce the optimal solution. The 0/1 Knapsack Problem is one such case, where dynamic programming gives the correct answer, but greedy fails.

---

Greedy algorithms offer simple, intuitive solutions with great performance for many problems. Understanding their limitations and identifying problems that fit their structure is key to using them effectively.