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.

Function Contract

max_non_overlapping_intervals(intervals) expects a list of (start, end) pairs.

It returns the maximum number of non-overlapping intervals under the convention that an interval ending at x does not overlap an interval starting at x. The greedy rule depends on sorting by earliest end time.

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.

The condition start >= current_end treats intervals as non-overlapping when one starts exactly where the previous one ends, such as half-open intervals. If a problem defines closed intervals as overlapping at shared endpoints, use the problem’s rule instead.

Why Greedy Is Hard

Greedy algorithms are easy to write and hard to justify. The question is not whether the local choice looks reasonable. The question is whether some optimal solution can always be transformed to include that local choice.

For interval scheduling, choosing the interval with the earliest end time is safe because it leaves the maximum remaining room for future intervals. Any solution that chose a later-ending first interval can swap in the earlier-ending interval without reducing the number of intervals that can follow.

Greedy Choice vs Exhaustive Choice

Backtracking tries multiple choices and may undo them. Dynamic programming compares choices through stored states. Greedy commits to one choice and moves on.

That commitment is why greedy can be fast, and also why it can be wrong.

Complexity

Many greedy algorithms are dominated by sorting, giving O(n log n) time. The selection pass after sorting is often O(n).

Some greedy algorithms avoid sorting and run in linear time, but only when the best local choice can be found directly.

How To Test the Idea

Before trusting a greedy rule, try to find a counterexample. Use small inputs and ask whether choosing the locally best option can block a better global result.

If no counterexample appears, the rule still needs an argument. A common argument is an exchange argument: show that any optimal solution can be changed to include the greedy choice without becoming worse.

Failure Example

For many problems, choosing the largest immediate value is not safe. A choice that looks best now can block several smaller choices that produce a better total.

A greedy rule needs a proof idea, often an exchange argument, showing that the local choice can be included in some optimal solution.

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.

Another common mistake is mixing greedy and hope. If an early choice might need to be revised later, the problem probably needs a different method.

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.

Do not use greedy just because it is simpler. Use it when the local choice can be defended.

The Main Point

Greedy is correct only when the local choice can be justified as safe. A plausible choice is not enough.