Module 4 · Graphs, greedy and interview polish Lesson 13 of 15
Greedy and intervals
A greedy solution takes the locally best choice and never reconsiders. It is right when the problem has that property - intervals sorted by end time is the classic case.
The concept
Greedy is easy to code and easy to get wrong; before trusting it, try to build a small counterexample. If you cannot, say why the greedy choice is safe.
Its tell is an exchange argument: swapping your choice for any other never improves the answer. Saying that sentence is worth as much as the code.
def max_meetings(intervals):
intervals.sort(key=lambda iv: iv[1]) # by END time
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end: # fits after the last one
count += 1
last_end = end
return count
# [[1,3],[2,4],[3,5]] -> 2 (take [1,3] then [3,5])Worked example
The maximum number of meetings in one room is greedy: sort by end time and take each meeting that starts after the last one ends.
Your practice task
Solve the meeting-room problem and write one sentence on why sorting by end time is the correct greedy choice.
Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.
Key takeaway
Greedy is easy to code and easy to get wrong; before trusting it, try to build a small counterexample.
Keep your place in this course
A free account saves which lessons you have finished and unlocks the certificate. The lesson itself stays free to read.
Create free account or sign inCourse complete
You finished every lesson.
Your certificate is ready, and the projects you built are the proof to attach to an application.
Almost there
15 lessons left of 15
Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.