Greedy algorithms

The idea

A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It never reconsiders its choices.

This works perfectly for problems like Activity Selection (Interval Scheduling): You want to attend the maximum number of non-overlapping meetings. If you sort them by end time and always pick the meeting that finishes earliest, you leave the maximum possible free time for remaining meetings!

Warning: Greedy fails if local choices lock you out of a hidden global optimum (e.g., the Knapsack problem).

How it works (Interval Scheduling)

def maxEvents(events):
    # Sort by end time! (The greedy choice)
    events.sort(key=lambda x: x[1])
    
    count = 0
    last_end = -float('inf')
    
    for start, end in events:
        if start >= last_end:
            count += 1
            last_end = end # Accept
            
    return count