A Greedy Algorithm is a problem-solving approach that builds up a solution step by step, always choosing the option that looks best at the moment (i.e., the local optimum), with the hope that this leads to a global optimum.

It makes a series of choices, each of which is greedy, meaning it selects the best choice without reconsidering previous decisions.

Technical Definition: A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding the global optimum.

 Properties of Greedy Algorithms

1. Greedy Choice Property: A globally optimal solution can be arrived at by selecting a local optimum.
2. Optimal Substructure: A problem has optimal substructure if an optimal solution contains optimal solutions to its subproblems.
3. No Reversal: Once a decision is made, it is never changed.
4. Feasibility Check: Ensures the current solution is valid.
5. Objective Function: There must be a clear way to compare possible choices.

Advantages

• Simple to implement and understand.
• Faster and more efficient than other methods like dynamic programming in some cases.
• Less memory usage since it doesn’t store previous states or results.
• Suitable for real-time systems where quick decisions are needed.

Drawbacks / Disadvantages

• Not always optimal: It may give a suboptimal or incorrect result if the problem doesn’t satisfy the greedy properties.
• Problem-specific: Only works well for certain problems (e.g., Huffman Coding, Kruskal’s, Prim’s).
• No backtracking: Once a wrong choice is made, it can’t be corrected.
• Fails in complex scenarios: Especially where current decisions heavily influence future choices.

Example: Activity Selection Problem

Problem Statement:

Given n activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can work on only one activity at a time.

Greedy Strategy:

Always select the next activity that finishes earliest and is non-overlapping with the previously selected one.

Steps (Working):

1. Sort activities by finish time:
   → A1 (3), A2 (5), A3 (6), A4 (7), A5 (8), A6 (9)
2. Pick A1 (finishes at 3)
3. Next non-overlapping activity → A3 (starts at 4, ends at 6)
4. Next non-overlapping activity → A4 (starts at 6, ends at 7)
5. Next non-overlapping activity → A6 (starts at 8, ends at 9)

Example Input:

Selected Activities: A1, A3, A4, A6 (Maximum 4 activities)

Greedy Algorithm Python code

# Generic greedy logic

def greedy_algorithm(problem):

    solution = []

    while not problem.is_solved():

        best_option = problem.get_best_greedy_choice()

        if problem.is_feasible(best_option):

            solution.append(best_option)

            problem.update_state(best_option)

    return solution

    Why Greedy Works:

The problem has greedy-choice property and optimal substructure, making the greedy strategy of choosing the earliest finishing activity lead to the optimal solution.