Greedy Algorithm in Data Structures

A Greedy Algorithm is an algorithmic paradigm that builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It makes the locally optimal choice at each step with the hope of finding a globally optimal solution.

Characteristics of Greedy Algorithms

• Greedy Choice Property: A global optimum can be reached by selecting a local optimum at each step.
• Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
• Not all problems can be solved greedily — they must satisfy these two properties.

When to Use Greedy Algorithms

• When the problem has the greedy choice property and optimal substructure.
• When you need an efficient, often simple, solution.
• When the problem is inherently amenable to a greedy strategy (e.g., scheduling, coin change, shortest path in some cases).

Classic Greedy Algorithm Examples

1. Activity Selection Problem

Given a set of activities with start and finish times, select the maximum number of activities that don't overlap. The greedy choice is to pick the activity with the earliest finish time.

def activity_selection(start, finish):
    n = len(start)
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    selected = [activities[0]]
    last_finish = activities[0][1]
    for i in range(1, n):
        if activities[i][0] >= last_finish:
            selected.append(activities[i])
            last_finish = activities[i][1]
    return selected

# Example
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish))  # Output: [(1,2), (3,4), (5,7), (8,9)]

2. Coin Change Problem (Greedy Version)

Given coin denominations, make change for a given amount using the fewest number of coins. The greedy choice is to use as many of the largest denomination as possible. Note: This works only for canonical coin systems (e.g., US coins).

def coin_change(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    if amount != 0:
        return None  # Cannot make exact change
    return result

print(coin_change([25, 10, 5, 1], 63))  # Output: [25, 25, 10, 1, 1, 1]

3. Huffman Coding

Used for lossless data compression. The greedy choice is to merge the two least frequent characters iteratively to build a prefix‑code tree.

4. Fractional Knapsack

Unlike the 0/1 knapsack, here items can be divided. The greedy choice is to take items with the highest value‑to‑weight ratio first.

def fractional_knapsack(items, capacity):
    # items: list of (value, weight)
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    total_value = 0.0
    for value, weight in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

Advantages & Disadvantages

Advantages

• Simple and easy to implement.
• Often very efficient (polynomial time).
• Provides quick solutions for many real‑world problems.

Disadvantages

• Does not always yield the optimal solution (requires verification).
• May fail on problems that require global optimization.
• Often requires proof of correctness to ensure global optimality.

Complexity

Applications

• Task scheduling (CPU, job scheduling).
• Minimum Spanning Tree (Kruskal's and Prim's algorithms).
• Shortest path (Dijkstra's algorithm).
• Data compression (Huffman coding).
• Network routing (greedy forwarding).