Greedy Algorithm
Learn Greedy Algorithm to boost your coding abilities
Definition
A greedy algorithm is a method used in problem-solving where, at each step, a locally optimal choice is made with the hope that these choices will lead to a globally optimal solution. The algorithm continuously selects the best option at each decision point without reconsidering choices once they’re made.
Core Idea
The fundamental principle behind a greedy algorithm is straightforward: at each stage, select the option that seems best at the moment, or “greediest” in terms of the desired outcome. By making these locally optimal choices, the algorithm aims to construct an overall solution that is as close as possible to the best possible solution for the problem as a whole. However, greedy algorithms are effective only when the problem has specific properties that guarantee that local optima lead to a global optimum.
For example, in a task scheduling problem, a greedy approach might prioritize tasks with the earliest end time to maximize the number of non-overlapping tasks. In cases where local decisions align with an optimal global solution, the greedy algorithm is highly efficient.
Common Applications
Greedy algorithms are widely used in various domains, especially in scenarios requiring optimal choices under constraints. Some of the common areas include:
- Scheduling Problems: Selecting tasks or jobs based on certain constraints, such as deadlines or times, to maximize resource utilization or minimize delays.
- Graph Theory: Many graph-related problems, such as finding the Minimum Spanning Tree (using Kruskal’s or Prim’s algorithm) or the shortest path in a weighted graph (Dijkstra’s algorithm), employ greedy methods.
- Optimization Problems: Problems such as the coin change problem, knapsack problem, and activity selection problem are well-suited to greedy strategies, where the aim is to maximize or minimize a certain parameter under constraints.
The effectiveness of greedy algorithms often depends on the problem’s structure, as not all problems can be optimally solved with a greedy approach. In cases where they are effective, greedy algorithms provide a highly efficient solution with minimal computation compared to more exhaustive approaches.
Key Characteristics of Greedy Algorithms
Greedy Choice Property
The greedy choice property is a defining characteristic of greedy algorithms. This property states that a global optimum can be reached by making a series of locally optimal choices — each choice at each step is the one that seems the best according to some criterion, without reconsidering previous choices.
For example, in the activity selection problem, where we want to maximize the number of non-overlapping activities in a schedule, the greedy approach chooses the activity with the earliest end time at each step. This local optimum (choosing the earliest ending activity) turns out to be part of the globally optimal solution, ensuring we maximize the number of activities without conflicts.
Optimal Substructure
Optimal substructure is another crucial property for a problem to be solvable by a greedy algorithm. This means that an optimal solution to the entire problem can be constructed from optimal solutions to its subproblems.
For instance, in the fractional knapsack problem, the solution involves taking items (or parts of items) that provide the highest value per weight. By solving subproblems — selecting parts of items one by one in a locally optimal way — the greedy algorithm arrives at a globally optimal solution, filling the knapsack to maximize value under the weight limit.
Greedy vs. Dynamic Programming
Both greedy algorithms and dynamic programming rely on the concept of optimal substructure, but they differ fundamentally in approach:
- Greedy Algorithms: Greedy algorithms make a single pass through the problem, making the best choice at each step. They are simpler and often more efficient in terms of time and space complexity but work only when the greedy choice property holds.
- Dynamic Programming: Dynamic programming considers all possible choices and breaks the problem into overlapping subproblems, which are solved and stored to avoid redundant calculations. Dynamic programming is used when there are multiple choices to evaluate, and we need to account for future consequences of each choice (e.g., problems where earlier choices affect later outcomes).
Examples of When to Use Each Approach:
- Greedy Algorithm Example: Coin Change Problem (when using a limited coin denomination system): Choosing the largest coin value possible at each step minimizes the total number of coins.
- Dynamic Programming Example: Fibonacci Sequence or 0/1 Knapsack Problem: These problems require evaluating multiple subproblems, where each choice affects future steps, making dynamic programming a more suitable solution.
Steps to Design a Greedy Algorithm
Designing a greedy algorithm involves carefully analyzing the problem to ensure that a greedy approach will yield an optimal solution. Here are the steps to follow:
Step 1: Identify the Problem Constraints and Requirements
- Start by thoroughly understanding the problem, its constraints, and what constitutes an optimal solution. Identify all relevant parameters, such as limits on input size, specific conditions, and any objective function that needs to be maximized or minimized.
- Example: In the coin change problem, the objective is to use the fewest coins to reach a target amount, given specific coin denominations. Constraints include the available denominations and the target amount.
Step 2: Determine if the Problem Exhibits the Greedy Choice Property
- Check if making a series of locally optimal choices will lead to a globally optimal solution. This involves confirming that each choice made along the way contributes directly to an optimal solution, without needing to reconsider previous decisions.
- Example: In the activity selection problem, choosing the activity with the earliest end time satisfies the greedy choice property because it maximizes the number of non-overlapping activities.
Step 3: Develop the Locally Optimal Strategy
- Formulate a strategy that makes the “greedy” choice at each step. This strategy should consistently select the best local option based on the problem’s criteria.
- Example: For the fractional knapsack problem, the greedy strategy is to choose items based on the highest value-to-weight ratio at each step, adding as much of the item as possible until the knapsack reaches its weight limit.
Step 4: Prove that the Greedy Choice Leads to an Optimal Solution
- This is often the most challenging step. Prove that the greedy approach yields an optimal solution for the entire problem by showing that local optimality implies global optimality.
- Mathematical induction or proof by contradiction can sometimes be useful to demonstrate the optimality of the greedy choice.
- Example: For the minimum spanning tree (MST) problem, we can prove that using algorithms like Kruskal’s or Prim’s, which make locally optimal choices to add edges with the least weight, will always yield an MST.
Step 5: Implement and Test the Solution
- Implement the greedy algorithm and thoroughly test it with various inputs, including edge cases, to ensure it performs correctly and optimally within the problem’s constraints.
- Analyze the time and space complexity to ensure that it’s efficient enough for large inputs.
- Example: For the coin change problem, implement the greedy algorithm and test it with different target amounts and coin denominations to verify it minimizes the coin count.
Examples of Greedy Algorithms
Let’s explore some classic problems where the greedy approach is effective.
Example 1: Coin Change Problem
Problem Statement: Given a set of coin denominations and a target amount, the goal is to find the minimum number of coins needed to make up that amount.
Greedy Solution:
- Sort the coins in descending order by denomination.
- Start with the largest coin and use as many of it as possible without exceeding the target amount.
- Subtract the value of these coins from the target amount.
- Move to the next largest denomination and repeat until the target amount is reached.
Step-by-Step Breakdown:
Suppose the target amount is 67, and the available denominations are [25, 10, 5, 1].
Start with the largest coin, 25, using 2 coins to get as close to 67 as possible (50).
The remaining amount is 67–50 = 17.
Move to the next coin, 10, and use 1 coin (total is now 60).
The remaining amount is 17–10 = 7.
Use 1 coin of 5 (total is now 65), leaving 2.
Use 2 coins of 1 to reach exactly 67.
Result: The minimum number of coins required is 2 (25) + 1 (10) + 1 (5) + 2 (1) = 6 coins.
Note: The greedy approach works well if the denominations allow a greedy solution (such as common U.S. coins). However, it may not always yield the optimal solution with arbitrary coin systems.
Example 2: Fractional Knapsack Problem
Problem Statement: Given a set of items, each with a weight and a value, and a knapsack with a weight limit, the objective is to maximize the total value in the knapsack. Unlike the 0/1 knapsack problem, the fractional knapsack problem allows taking fractional parts of items.
Greedy Solution:
- Sort items by their value-to-weight ratio in descending order.
- Start with the item with the highest value-to-weight ratio, adding as much as possible to the knapsack until reaching the weight limit.
- If the weight of an item exceeds the remaining weight capacity, add a fraction of it instead.
Step-by-Step Breakdown:
Suppose the knapsack capacity is 50 units, with three items having the following properties:
- Item A: weight = 10, value = 60, ratio = 6
- Item B: weight = 20, value = 100, ratio = 5
- Item C: weight = 30, value = 120, ratio = 4
Sort items by value-to-weight ratio: A > B > C.
Get Kapil Bhardwaj’s stories in your inbox
Join Medium for free to get updates from this writer.
Add Item A entirely (10 units, 60 value).
Add Item B entirely (20 units, 100 value).
Add as much of Item C as possible with remaining 20 units of capacity.
Since Item C’s total weight is 30, take 20/30 of Item C, which gives a value of 120×2030=80120 \times \frac{20}{30} = 80120×3020=80.
Result: The maximum value in the knapsack is 60 (A) + 100 (B) + 80 © = 240.
Example 3: Activity Selection Problem
Problem Statement: Given a set of activities, each with a start and end time, select the maximum number of non-overlapping activities.
Greedy Solution:
- Sort activities by their end times in ascending order.
- Select the first activity (which has the earliest end time).
- For each subsequent activity, if it starts after or when the previous activity ends, select it.
Step-by-Step Breakdown:
Suppose we have activities with start and end times as follows:
- Activity 1: (start = 1, end = 4)
- Activity 2: (start = 3, end = 5)
- Activity 3: (start = 0, end = 6)
- Activity 4: (start = 5, end = 7)
- Activity 5: (start = 8, end = 9)
Sort activities by end time: Activity 1 (end = 4), Activity 2 (end = 5), Activity 4 (end = 7), Activity 5 (end = 9), Activity 3 (end = 6).
Select Activity 1 as it ends first.
Skip Activity 2, as it starts before Activity 1 ends.
Select Activity 4, as it starts after Activity 1 ends.
Select Activity 5, as it starts after Activity 4 ends.
Result: The selected activities are 1, 4, and 5, allowing the maximum number of non-overlapping activities.
Greedy Algorithm Practice Problems
Here’s a list of popular greedy algorithm problems along with brief tips on how to approach each. Practicing these problems can help build an understanding of the greedy choice property and optimal substructure.
1. Coin Change Problem
- Problem: Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up the amount.
- Approach: Sort the coins in descending order, use the largest denomination as much as possible, and then proceed with the next largest. Note that this approach works effectively if the denominations allow a greedy solution (like in U.S. currency).
def coin_change(coins, amount):
coins.sort(reverse=True) # Sort coins in descending order
count = 0
for coin in coins:
count += amount // coin # Use as many coins of this denomination as possible
amount %= coin # Reduce the remaining amount
return count if amount == 0 else -1 # Return -1 if it's not possible
# Example usage:
coins = [25, 10, 5, 1]
amount = 67
print(coin_change(coins, amount)) # Output: 62. Fractional Knapsack Problem
- Problem: Given a set of items, each with a weight and value, and a maximum weight capacity, maximize the total value by taking fractional amounts of items if needed.
- Approach: Calculate the value-to-weight ratio of each item, then sort items by this ratio in descending order. Add items or fractions of them in this order until reaching the weight limit.
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True) # Sort by value-to-weight ratio
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
# Example usage:
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50
print(fractional_knapsack(items, capacity)) # Output: 240.03. Activity Selection Problem
- Problem: Given a set of activities with start and end times, select the maximum number of non-overlapping activities.
- Approach: Sort activities by end times, then select the earliest finishing activity and continue with the next compatible activity that starts after the previous one ends.
def activity_selection(activities):
activities.sort(key=lambda x: x[1]) # Sort by end time
selected_activities = [activities[0]] # Always pick the first activity
for i in range(1, len(activities)):
if activities[i][0] >= selected_activities[-1][1]: # Check for non-overlapping
selected_activities.append(activities[i])
return selected_activities
# Example usage:
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(activity_selection(activities)) # Output: [(1, 4), (5, 7), (8, 9)]4. Minimum Spanning Tree (MST)
- Problem: Given a graph, find the subset of edges that connects all vertices with the minimum possible total edge weight, without any cycles.
- Approach: Use Kruskal’s or Prim’s algorithm, both of which are greedy. Kruskal’s adds the smallest edge while avoiding cycles, and Prim’s starts from a vertex, expanding the MST by the smallest adjacent edge.
class Edge:
def __init__(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
def kruskal_mst(edges, num_nodes):
edges.sort(key=lambda x: x.weight) # Sort edges by weight
parent = list(range(num_nodes))
def find(u):
if u != parent[u]:
parent[u] = find(parent[u])
return parent[u]
mst_weight = 0
for edge in edges:
u_root = find(edge.u)
v_root = find(edge.v)
if u_root != v_root:
mst_weight += edge.weight
parent[u_root] = v_root
return mst_weight
# Example usage:
edges = [Edge(0, 1, 10), Edge(0, 2, 6), Edge(0, 3, 5), Edge(1, 3, 15), Edge(2, 3, 4)]
print(kruskal_mst(edges, 4)) # Output: MST weight5. Huffman Coding
- Problem: Given frequencies of characters, construct an optimal prefix-free binary code for data compression.
- Approach: Use a priority queue to combine the two least frequent characters repeatedly until only one tree remains. The greedy choice at each step ensures the optimal encoding length.
import heapq
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_code(frequencies):
heap = [Node(char, freq) for char, freq in frequencies.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq)
merged.left, merged.right = left, right
heapq.heappush(heap, merged)
def generate_codes(node, current_code, codes):
if node:
if node.char is not None:
codes[node.char] = current_code
generate_codes(node.left, current_code + '0', codes)
generate_codes(node.right, current_code + '1', codes)
return codes
return generate_codes(heap[0], "", {})
# Example usage:
frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
print(huffman_code(frequencies)) # Output: Huffman codes for each character6. Job Sequencing Problem
- Problem: Given a set of jobs with deadlines and profits, schedule the jobs to maximize total profit, ensuring each job is completed before its deadline.
- Approach: Sort jobs by profit in descending order, and schedule each job in the latest available slot before its deadline to maximize profit.
def job_sequencing(jobs, max_deadline):
jobs.sort(key=lambda x: -x[1]) # Sort jobs by profit in descending order
result = [-1] * max_deadline
max_profit = 0
for job in jobs:
for j in range(min(max_deadline, job[0]) - 1, -1, -1):
if result[j] == -1:
result[j] = job[1]
max_profit += job[1]
break
return max_profit
# Example usage:
jobs = [(2, 100), (1, 50), (2, 10), (1, 20), (3, 30)] # (deadline, profit)
max_deadline = 3
print(job_sequencing(jobs, max_deadline)) # Output: Maximum profit7. Egyptian Fraction Problem
- Problem: Express a given fraction as a sum of unique unit fractions.
- Approach: Repeatedly take the largest possible unit fraction (starting with 1/ceil(denominator/numerator)) until the fraction is reduced to zero.
from math import ceil
def egyptian_fraction(numerator, denominator):
result = []
while numerator != 0:
x = ceil(denominator / numerator)
result.append(f"1/{x}")
numerator = x * numerator - denominator
denominator *= x
return result
# Example usage:
print(egyptian_fraction(6, 14)) # Output: Egyptian fraction representation8. Largest Number Problem
- Problem: Given a list of non-negative integers, arrange them to form the largest possible number.
- Approach: Sort numbers as strings, choosing a custom comparator that arranges pairs (a, b) so that concatenating
a + bresults in a larger number thanb + a.
from functools import cmp_to_key
def largest_number(nums):
nums = list(map(str, nums))
nums.sort(key=cmp_to_key(lambda x, y: 1 if x + y < y + x else -1))
return ''.join(nums).lstrip('0') or '0'
# Example usage:
nums = [3, 30, 34, 5, 9]
print(largest_number(nums)) # Output: "9534330"9. Maximum Number of Platforms Required (Train Arrival and Departure)
- Problem: Given train arrival and departure times, find the minimum number of platforms needed so no two trains overlap on the same platform.
- Approach: Sort both arrival and departure times, and use two pointers to track overlapping intervals, incrementing the count of platforms as needed.
def min_platforms(arrivals, departures):
arrivals.sort()
departures.sort()
platforms_needed, max_platforms = 0, 0
i = j = 0
while i < len(arrivals):
if arrivals[i] < departures[j]:
platforms_needed += 1
i += 1
max_platforms = max(max_platforms, platforms_needed)
else:
platforms_needed -= 1
j += 1
return max_platforms
# Example usage:
arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms(arrivals, departures)) # Output: Minimum number of platforms required10. Gas Station Problem
- Problem: Given a circular route with gas stations, each providing gas and requiring gas to reach the next station, determine if there’s a starting point that completes the circuit.
- Approach: Use a greedy approach to track cumulative gas balance and restart from the next station whenever a station cannot be reached.
def can_complete_circuit(gas, cost):
total_gas = total_cost = start = tank = 0
for i in range(len(gas)):
total_gas += gas[i]
total_cost += cost[i]
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start if total_gas >= total_cost else -1
# Example usage:
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost)) # Output: Starting index for completing the circuitConclusion
Summary: In this article, we explored greedy algorithms in depth, covering their core characteristics, the process of designing a greedy algorithm, and examples of some classic greedy problems, each with an illustrative Python solution. Greedy algorithms excel at solving optimization problems by making the best immediate choice at each step, aiming to lead to an overall optimal solution. With a range of applications across fields like scheduling, resource allocation, and graph theory, understanding the principles of greedy algorithms is essential for solving various real-world problems efficiently.
Final Tips: Mastering greedy algorithms requires a blend of theoretical knowledge and practical problem-solving skills. Here are a few tips for advancing your understanding:
- Practice Diverse Problems: Try a variety of greedy algorithm problems to recognize patterns and scenarios where the greedy approach works best, especially problems involving sorting, resource allocation, and selection.
- Analyze Problem Constraints: Some problems appear suited for a greedy solution but require dynamic programming or another approach. Carefully analyze problem constraints and check for the greedy choice property and optimal substructure to confirm that a greedy solution is appropriate.
- Optimize Through Code: As you practice, focus on implementing your greedy solutions efficiently. Aim to use data structures like heaps, sorted lists, and priority queues to ensure your solution is both optimal and performs well on large inputs.
~~Thanks for reading and supporting.
Stackademic 🎓
Thank you for reading until the end. Before you go:
- Please consider clapping and following the writer! 👏
- Follow us X | LinkedIn | YouTube | Discord | Newsletter | Podcast
- Create a free AI-powered blog on Differ.
- More content at Stackademic.com






