Greedy Algorithms: Activity Selection and Coin Change Problem

---

Table of Contents

1. Introduction to Greedy Algorithms
2. Activity Selection Problem
3. Code Example: Activity Selection Problem
4. Coin Change Problem (Greedy Approach)
5. Code Example: Coin Change Problem
6. Real-World Applications and Limitations
7. Frequently Asked Questions
8. Conclusion

Introduction to Greedy Algorithms

Greedy Algorithms are one of the most intuitive, efficient, and widely-used strategies in computer science and optimization. The core idea is simple: at each step, make the locally optimal choice with the hope that these choices will lead to the globally best solution[7][10][18]. This approach is typically faster and easier to implement than other techniques such as dynamic programming or backtracking. However, greedy methods do not always guarantee the optimal solution for all problems.

“Living in the present. Don’t overthink about the future – that’s the philosophy of greedy algorithms.”

• Fast: Greedy algorithms are typically fast as they only need to consider the best choice at each stage.
• Efficient: Lower space complexity as they don't retain past decisions.
• Optimal for Some Problems: While greedy methods don't always give the global optimum, some problems, like Activity Selection and certain forms of Coin Change, are solvable optimally using this approach[1][11][12].

Activity Selection Problem

The Activity Selection Problem is a classic example that demonstrates the power of the greedy approach. The goal is to select the maximum number of activities that don't overlap in time from a given set of activities, each with a start and finish time[1][3][5].

Problem Statement

• You are given n activities, each with a start time and a finish time.
• Choose the maximum subset of mutually non-overlapping activities that a single person can perform.

Example

Input: start[] = [1,3,0,5,8,5], finish[] = [2,4,6,7,9,9]
Output: 4
Explanation: The person can perform at most four activities: [0, 1, 3, 4] (these are indexes in the input array[1]).

How the Greedy Choice Works

• Sort the activities based on their finish times (earliest first).
• Pick the activity with the smallest finish time first.
• For each subsequent activity, choose it if its start time is after or equal to the finish time of the last selected activity.
• Repeat until no more activities can be included.

Proof of Correctness: Choosing activities that finish earliest leaves the most room for future activities, maximizing the number of non-overlapping activities[1][3][8].

Algorithm (Pseudocode)

Greedy-Iterative-Activity-Selector(S, start, finish):
    Sort activities by finish times
    S = []
    S.append(activity with earliest finish)
    for activity in activities[1...n]:
        if activity.start >= last_activity.finish:
            S.append(activity)
    return S
    

Time Complexity: O(n log n) (mainly for the sorting step)[8][11].

Code Example: Activity Selection in Python

# Activity Selection Problem (Greedy)
def activity_selection(start, finish):
    n = len(start)
    # Pair and sort by finish time
    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 usage
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
result = activity_selection(start, finish)
print("Selected activities:", result)
    

Output: Selected activities: [(1, 2), (3, 4), (5, 7), (8, 9)]

Coin Change Problem: Greedy Approach

The Minimum Coin Change problem asks for the smallest number of coins needed to make up a specific amount, given coin denominations[6][12][13].

Greedy Strategy

• Always select the coin of the largest denomination less than or equal to the remaining amount.
• Repeat until the amount becomes zero.

Step-by-Step Example

Denominations: [25, 10, 5, 1]
Make change for: 63

1. Select 25: 63-25=38 (count=1)
2. Select 25: 38-25=13 (count=2)
3. Select 10: 13-10=3 (count=3)
4. Select 1: 3-1=2 (count=4)
5. Select 1: 2-1=1 (count=5)
6. Select 1: 1-1=0 (count=6)

Result: Minimum coins used = 6; Coin set: [25, 25, 10, 1, 1, 1][6][13].

When Greedy Fails

Greedy approach works only when the coin denominations are "canonical" (the system supports greedy optimality). For denominations like [1, 3, 4] and value 6, the greedy output is [4,1,1]=3 coins (not optimal); dynamic programming finds [3,3]=2 coins.

Greedy is optimal for Indian and US coin systems, but not all arbitrary coin sets[12][19].

Time Complexity: O(n) where n is the number of denominations.

Code Example: Coin Change (Greedy) in Python

# Coin Change Problem (Greedy)
def coin_change_greedy(denominations, value):
    denominations.sort(reverse=True)
    result = []
    for coin in denominations:
        while value >= coin:
            value -= coin
            result.append(coin)
    return result

# Example usage
denominations = [25, 10, 5, 1]
value = 63
change = coin_change_greedy(denominations, value)
print("Coin set:", change)
print("Minimum coins needed:", len(change))
    

Output: Coin set: [25, 25, 10, 1, 1, 1]
Minimum coins needed: 6

Real-World Applications and Limitations of Greedy Algorithms

Applications

• Job Scheduling and Planning (Activity Selection)
• Currency Change Machines (Coin Change)
• Network Routing (Dijkstra's, Prim's)
• Data Compression (Huffman coding)
• Minimum Spanning Tree (Kruskal’s, Prim’s Algorithm)
• Resource Allocation
• Fractional Knapsack

Limitations

• Not always globally optimal (fails for some Coin Change inputs)
• Lacks lookahead or reconsideration of previous choices
• Dynamic Programming is needed for globally optimal solutions when greedy fails[12][19]

Frequently Asked Questions

Q1. What makes a problem greedy-approachable?

Problems that exhibit greedy-choice property and optimal substructure can often be solved optimally using greedy methods[7][10].

Q2. Is greedy better than dynamic programming?

Greedy is faster and simpler. However, DP guarantees an optimal solution for a broader class of problems. Use greedy when you can prove its optimality.

Q3. When does greedy fail for Coin Change?

Greedy fails for Coin Change when denominations are not “canonical,” i.e., picking the largest coin doesn't guarantee the minimum number of coins. Use DP for arbitrary coin sets[12][19].

Q4. Can greedy be used for fractional knapsack?

Yes. Unlike 0/1 knapsack, the fractional knapsack problem is optimally solvable by greedy[7][18].

Conclusion

Greedy algorithms offer powerful, efficient solutions for a range of optimization problems. Mastering classics like Activity Selection and Coin Change gives you deep insight into choosing locally optimal steps and understanding their impact. Always analyze the problem’s structure for the greedy-choice property before applying this strategy for best results.

---