Greedy algorithms make the locally optimal choice at each step, hoping that leads to the global optimum. They're simple, fast, and surprisingly powerful! 🏃♂️
💡 Think of it like this: You're at a buffet and can only carry one plate. At each food station, you grab the best-looking item. You never go back to change your mind. Sometimes this gives you the best meal, sometimes it doesn't — but when it works, it's the fastest strategy!
When does Greedy work? When the problem has the greedy choice property: making the locally best choice at each step leads to the globally best answer.
# Classic: Activity Selection (scheduling meetings)
# Given activities with start/end times, pick the MOST non-overlapping ones
# Greedy: Always pick the one that ENDS earliest!
activities = [(1,3), (2,5), (3,4), (5,7), (6,8)]
activities.sort(key=lambda x: x[1]) # Sort by end time
selected = [activities[0]] # Pick first (ends earliest)
for start, end in activities[1:]:
if start >= selected[-1][1]: # Doesn't overlap?
selected.append((start, end)) # Pick it!
# selected = [(1,3), (3,4), (5,7)] → 3 activities ✓
📋 Instructions
Find the maximum number of non-overlapping activities.
Activities: [(1,4),(3,5),(0,6),(5,7),(3,8),(5,9),(6,10),(8,11),(8,12),(2,13),(12,14)]
Sort by end time and greedily select.
Sort by end time. Pick first activity. For each next, if start >= last selected end, pick it.