Understanding Greedy Algorithms

Introduction

Greedy algorithms are a simple yet powerful problem-solving technique. The idea is to make the best possible choice at each step, aiming to achieve the optimal overall result.

Greedy algorithms do not backtrack or reconsider previous decisions. They work well when the local optimal choice leads to a global optimal solution.

Greedy algorithms are used in:

• Scheduling

• Optimization problems

• Graph algorithms (Prim’s, Kruskal’s)

• Resource allocation

Key Idea of Greedy Algorithms

At every step:

1. Choose the best available option

2. Never reconsider earlier choices

3. Move to the next step

This approach is simple, fast, and works for many real-world scenarios.

When Do Greedy Algorithms Work?

A greedy algorithm works only when the problem has:

1. Greedy-choice property

A global optimum can be reached by choosing a local optimum.

2. Optimal substructure

The optimal solution to a problem contains optimal solutions to its subproblems.

If a problem does not satisfy these, greedy algorithms may give the wrong answer.

Example 1: Activity Selection Problem

You are given the start and end times of activities. Choose the maximum number of activities that do not overlap.

Greedy Strategy

Always pick the activity that ends earliest.

Example

Activities (start, end):

(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)

Sorted by end time:

(1,4), (3,5), (5,7), (8,9)

Result ? 4 activities

C# Implementation

int MaxActivities(int[] start, int[] end)
{
    int n = start.Length;

    int count = 1;
    int last = 0;

    for (int i = 1; i < n; i++)
    {
        if (start[i] >= end[last])
        {
            count++;
            last = i;
        }
    }

    return count;
}

Example 2: Fractional Knapsack Problem

You can take fractions of items. Choose items to maximize value.

Greedy Strategy

Pick items with the highest value/weight ratio.

This ensures the maximum value per unit of weight.

Time Complexity

O(n log n) (sorting by ratio)

Example 3: Minimum Number of Coins

Given coins of certain denominations, find the minimum number needed to reach a given value.

Greedy Strategy

Always take the largest coin possible.

Example

Coins: 1, 2, 5, 10
Value: 27

Steps:

Take 10 ? 17
Take 10 ? 7
Take 5 ? 2
Take 2 ? 0

Coins used = 4

C# Implementation

int MinCoins(int[] coins, int amount)
{
    Array.Sort(coins);
    Array.Reverse(coins);

    int count = 0;

    foreach (var coin in coins)
    {
        while (amount >= coin)
        {
            amount -= coin;
            count++;
        }
    }

    return count;
}

Real-Life Applications of Greedy Algorithms

1. Huffman Coding (Data Compression)

Greedy choice builds optimal prefix codes.

2. Minimum Spanning Tree

• Prim’s algorithm

• Kruskal’s algorithm

3. Dijkstra’s Algorithm

Finds the shortest path from the source to all nodes.

4. CPU Scheduling

Choosing the earliest finishing or the shortest job.

5. Cache Optimization

Choosing the least frequently or least recently used items.

Advantages of Greedy Algorithms

• Simple to understand

• Fast execution

• No recursion required

• Works well for many optimization problems

Disadvantages of Greedy Algorithms

• Does not always produce the optimal result

• Works only for specific types of problems

Summary

Greedy algorithms make the best choice at each step without considering future steps. They are simple, efficient, and extremely useful in optimization and graph-related problems.

Key takeaways:

• Works when the local optimum leads to the global optimum

• Used in MST, shortest paths, scheduling, and compression

• Faster and simpler than dynamic programming or backtracking