Greedy Algorithms

Greedy algorithms are a class of algorithms that make locally optimal choices at each step in hopes of achieving a globally optimal solution. They are used in a wide range of applications, including optimization problems and scheduling algorithms where a minimum or maximum possible result is expected.

In this blog post, we will explore the concept of greedy algorithms and provide some example code snippets using Python.

The Greedy Algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In general, greedy algorithms make decisions that lead to the optimal result, but that does not always guarantee a globally optimal solution.

The following are the steps involved in a greedy algorithm:

1. Initialization: Set the initial state of the problem.

2. Selection: Select the best option available at the current step.

3. Evaluation: Evaluate the selected option to see if it leads to the optimal solution.

4. Termination: Repeat steps 2-3 until a solution is found.

However, this algorithm cannot be used in all problems.

When to use the Greedy Algorithm

Problems in which this approach could be used have two properties,

1. Greedy-choice property: A global optimum can be arrived at by selecting a local optimum.

2. Optimal Substructure: An optimal solution to the problem contains an optimal solution to subproblems.

This may sound familiar with dynamic programming. However, the difference is that the Greedy algorithm never reconsiders its choices.

Greedy algorithms are often used to solve optimization problems, where the goal is to find the best solution from a set of possible solutions. For example, the famous Knapsack problem can be solved using a greedy algorithm.

Example: Interval Scheduling

One example of a problem that can be solved using a greedy algorithm is the interval scheduling problem. In this problem, we are given a set of tasks, each with a start time and an end time. Our goal is to select as many tasks as possible, without overlapping.

Here's how the greedy algorithm for interval scheduling works:

1. Initialization: Sort the tasks by their end times, in ascending order.

2. Selection: Select the first task in the sorted list.

3. Evaluation: Iterate through the remaining tasks, selecting any task that does not overlap with the previously selected task.

4. Termination: Repeat steps 2-3 until there are no more tasks left.

Let's take a look at the Python code for interval scheduling:

def interval_scheduling(tasks):
    tasks.sort(key=lambda x: x[1]) # sort by end time
    selected_tasks = []
    
    for task in tasks:
        if not selected_tasks or task[0] >= selected_tasks[-1][1]:
            selected_tasks.append(task)
    
    return selected_tasks

In the above code, we first sort the tasks by their end times. Then, we iterate through the sorted tasks, selecting any task that does not overlap with the previously selected task. The selected tasks are stored in a list and returned at the end.

Example: Minimum Spanning Tree

Another example of a problem that can be solved using a greedy algorithm is the Minimum Spanning Tree problem. In this problem, we are given a connected, undirected graph with weighted edges. Our goal is to find the tree that spans all the vertices with the minimum possible total edge weight.

Here's how the greedy algorithm for Minimum Spanning Tree works:

1. Initialization: Create a set of all the vertices in the graph.

2. Selection: Select the edge with the minimum weight.

3. Evaluation: Iterate through the remaining edges, adding any edge that does not create a cycle.

4. Termination: Repeat steps 2-3 until there are no more edges left.

Let's take a look at the Python code for Minimum Spanning Tree:

def minimum_spanning_tree(graph):
    vertices = set(graph.keys())
    mst = set()
    
    while vertices:
        if not mst:
            vertex = vertices.pop()
        else:
            possible_edges = [(u, v, w) for (u, v, w) in graph.edges() if u in mst and v not in mst or v in mst and u not in mst]
            edge = min(

Pros - Simple, runs fast, easy to implement

Cons - Very often they don't provide a globally optimum solution.

Applications of Greedy Algorithm

• Used for Constructing Minimum Spanning Trees: Prim’s and Kruskal’s Algorithms used to construct minimum spanning trees are greedy algorithms.

• Used to Implement Huffman Encoding: A greedy algorithm is utilized to build a Huffman tree that compresses a given image, spreadsheet, or video into a lossless compressed file.

• Used to Solve Optimization Problems: Graph - Map Coloring, Graph - Vertex Cover, Knapsack Problem, Job Scheduling Problem, and activity selection problems are classic optimization problems solved using a greedy algorithmic paradigm.