DSA Greedy Algorithms

Definition

A greedy algorithm picks the most favorable option available at each moment, aiming to reach the best overall outcome by trusting every step's instant gain.

Unlike brute-force methods that explore every possible outcome, greedy algorithms try to be smart by always going for what looks best at the moment.

Key Idea (Uniquely Explained)

It behaves like a person trying to collect the maximum number of coins by always picking the biggest coin they see first — even if that doesn’t always lead to the perfect total in the end.

When It Works Well

• The problem must have a property called the Greedy Choice Property: making a local optimal choice leads to a global optimum.
• Optimal substructure means you can solve smaller chunks of the problem perfectly, and when combined, they still form the best solution for the entire task.

How It Works – Unique Step-by-Step

• Start with the full problem.
• At each stage, pick the option that gives the biggest benefit right now.
• Continue solving the leftover portion by applying the same greedy step to what's still unresolved.
• Stop when you reach the goal.

You don’t look back or change your mind.

Simple & Unique Example

Problem: From a set of tasks marked by their start and finish times, select the largest group that can be scheduled without any time clashes.

Input:

Activities:  
A1 (start=1, end=3) 
A2 (start=2, end=4) 
A3 (start=3, end=5) 
A4 (start=0, end=6)

Greedy Approach

• Sort by end time.
• Pick the first activity.
• Only choose the next task if it begins strictly after the previous one finishes to avoid any overlap.

OutPut:

Choose A1 and A3 – they don’t overlap and give the maximum count.

Common Greedy Algorithms

• Fractional Knapsack: Take the highest value-to-weight ratio items first, even if partially.
• Huffman Encoding: Build the most efficient binary codes by combining the least frequent characters.
• Dijkstra’s Algorithm: Always move to the nearest unvisited node to find shortest paths in a weighted graph.
• Prim’s Algorithm grows the spanning tree by repeatedly attaching the lightest possible edge that links a new node to the current connected set.

Where Greedy Fails

Greedy doesn't always give the best result — especially in problems like 0/1 Knapsack, where taking the obvious best item first might block better choices later.

Real-Life Analogy (Unique)

Imagine you're filling your backpack with snacks. You always pick the tastiest-looking one without checking if there's a better combination. At times, choices align perfectly; other times, the best options slip away unnoticed.

Pros and Cons

Advantages:

• Simple to implement.
• Fast and uses fewer resources.
• Works great when the greedy choice leads to an optimal answer.

Disadvantages:

• Can give incorrect results if the problem lacks the required properties.
• Doesn’t reconsider earlier choices.

Summary

Greedy algorithms make decisions based only on what looks best at the moment. They're fast and clever — but only reliable when the problem structure guarantees that local decisions build the right overall solution.