After this lesson, you will be able to: Understand the greedy choice property, recognize when greedy works and when it fails, and apply it to classic problems like activity selection and Dijkstra's algorithm.
A greedy algorithm makes the choice that looks best right now and never reconsiders. When the problem has the right structure, greedy is simpler and faster than dynamic programming. The hard part is knowing when greedy is actually correct, because it often looks right but gives wrong answers.
Greedy works when a locally optimal choice leads to a globally optimal solution. At each step you grab the best immediate option and commit, never backtracking. Compared to DP, which explores subproblems and combines them, greedy just charges forward. When it works it is usually O(n log n) or better. The catch: greedy is correct only when the problem provably has the greedy choice property, and proving that is the real skill.
Schedule the most non-overlapping meetings. Pick by earliest finish time.
def max_activities(intervals):# Greedy: always take the activity that finishes earliest.intervals.sort(key=lambda x: x[1]) # sort by finish timecount, last_end = 0, float('-inf')for start, end in intervals:if start >= last_end: # no overlap with the last chosencount += 1last_end = endreturn count# [(1,3),(2,4),(3,5),(0,6)] -> 2 (e.g., (1,3) then (3,5))# Why earliest finish? It leaves the most room for future activities.
Dijkstra's shortest-path algorithm is greedy: it always expands the closest unvisited node next, using a min-heap. Huffman coding (data compression) greedily merges the two least-frequent symbols. Interval scheduling, fractional knapsack, and minimum spanning trees (Prim's and Kruskal's) are all greedy. These are proven correct; that is why they are trusted. You will see Dijkstra again in the graph algorithms lesson.
Do not trust greedy by default. Test it.
1. Formulate the greedy rule (what is the 'best immediate choice'?).
2. Try to construct a counterexample where the greedy choice leads to a worse overall result.
3. If you find one, greedy is wrong; reach for DP or another approach.
4. If you cannot, sketch an exchange argument: show any optimal solution can be transformed to start with the greedy choice without getting worse.
5. In an interview, say explicitly 'greedy works here because...' or 'greedy fails here, so I will use DP.'
Assuming greedy works because it feels right and skipping the counterexample check (the single most common greedy error). Confusing greedy with DP (greedy commits and never reconsiders; DP explores). Sorting by the wrong key (activity selection needs earliest finish, not earliest start or shortest duration). Applying greedy coin change to arbitrary coin systems. Not stating your justification, which interviewers specifically probe for.
Sign in and purchase access to unlock this lesson.