Classic Greedy Algorithm Examples and Applications

In the previous article, we explored the differences between greedy algorithms and dynamic programming, highlighting their respective suitability for different types of problems. Greedy algorithms are generally simpler and more efficient strategies, commonly applied to optimization problems. Next, we will delve into several classic greedy algorithm examples to better understand their practical applications and implementations.

Overview of Greedy Algorithms

A greedy algorithm is a constructive algorithm that builds an overall optimal solution by making locally optimal choices at each step. It typically involves the following steps:

1. Select a locally optimal choice: At each step, choose the option that appears best at that moment.
2. Define a termination condition: Ensure that, upon completion of selections, one can correctly determine whether the global optimum has been achieved.
3. Prove that local optimality leads to global optimality: Verify that selecting a particular locally optimal choice does not compromise the final optimal solution.

Classic Greedy Algorithm Examples

1. Coin Change Problem

In the coin change problem, we are given an unlimited supply of coins of various denominations and must make change for a given amount using the fewest possible coins. Suppose we have coins of denominations 1, 3, and 4, and need to make change for amount 6.

Solution

We apply a greedy strategy by always selecting the largest denomination coin feasible. The steps are as follows:

1. Select a coin of denomination 4 → remaining amount = $6 - 4 = 2$.
2. Cover the remaining amount 2 with two coins of denomination 1.

The resulting combination is: one coin of denomination 4 and two coins of denomination 1 — totaling three coins.

Code Implementation

def coin_change(coins, amount):
    coins.sort(reverse=True)  # Sort in descending order
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

coins = [4, 3, 1]
amount = 6
print(coin_change(coins, amount))  # Output: 3

2. Activity Selection Problem

The activity selection problem is a classic scheduling problem where the goal is to select the maximum number of non-overlapping activities. Assume the start and finish times of the activities are as shown in the table below.

Solution

This problem can be solved by greedily selecting the activity with the earliest finish time. The procedure is as follows:

1. Sort all activities by their finish times.
2. Select the first activity; then iteratively select the next activity whose start time does not overlap with the finish time of the last selected activity.

Code Implementation

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # Sort by finish time
    selected = [activities[0]]  # Select the first activity
    last_end_time = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end_time:  # No overlap
            selected.append(activities[i])
            last_end_time = activities[i][1]
    
    return selected

activities = [(1, 3), (2, 5), (4, 6), (5, 7), (3, 4)]
print(activity_selection(activities))  # Output: [(1, 3), (4, 6), (5, 7)]

3. Minimum Spanning Tree (Kruskal’s Algorithm)

The minimum spanning tree (MST) problem asks us to select a subset of edges from a weighted undirected graph such that all vertices are connected and the total edge weight is minimized. Kruskal’s algorithm is a greedy approach to solving this problem.

Solution

Kruskal’s algorithm proceeds as follows:

1. Sort all edges in ascending order of weight.
2. Starting from the lightest edge, add it to the MST if doing so does not create a cycle.

Code Implementation

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]
    
    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            self.parent[rootP] = rootQ

def kruskal(num_vertices, edges):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    uf = UnionFind(num_vertices)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):  # Adding edge won't form a cycle
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(kruskal(4, edges))

Summary

In this article, we examined several classic applications of greedy algorithms. We observed that greedy algorithms excel in many optimization problems — their effectiveness hinges on how “local optimality” is defined and rigorously verified to guarantee “global optimality.” Although conceptually simple, greedy algorithms require careful validation of correctness when applied to real-world problems.

In the next article, we will discuss complexity analysis and optimization — particularly how to compute time complexity. This is a crucial aspect of programming, and we encourage you to stay tuned.