Greedy

A greedy algorithm makes the best-looking local choice at each step and does not go back to revise earlier choices.

Greedy algorithms can be very efficient, but they are correct only when the problem has the right structure.

Core Idea

The algorithm needs a rule for choosing the next item, edge, interval, or action. The hard part is proving that this local choice can still lead to a globally optimal answer.

Sorting often appears before greedy selection because it makes the local choice easy to apply in a controlled order.

Python Example

def max_non_overlapping_intervals(intervals):
    intervals = sorted(intervals, key=lambda interval: interval[1])
    count = 0
    current_end = float("-inf")
 
    for start, end in intervals:
        if start >= current_end:
            count += 1
            current_end = end
 
    return count

Choosing the interval that ends earliest leaves as much room as possible for later intervals.

Common Confusions

Greedy does not mean “choose the biggest value” in every problem. The local rule depends on the structure of the problem.

A greedy algorithm that works on examples may still be wrong. The local choice needs a correctness argument.

When To Use It

Use greedy thinking when a problem asks for an optimum and there may be a local choice that never hurts the future. Be especially careful to test and justify the choice rule.