Algorithms (CS 301) Greedy Interval Scheduling and Exchange Argument Exam Review
Carnegie Mellon University
Algorithms (CS 301) | Exam Review

Overview
An exam review on greedy interval scheduling, including the exchange argument proof pattern that often appears on algorithm exams.

Key topics
•earliest finish time criterion
•proof via exchange argument
•counterexamples to wrong greedy rules
•runtime analysis

Suggested study tasks
•explain why earliest finish is optimal using an exchange argument
•spot a wrong greedy rule and give a counterexample
•write clean runtime for sort + scan

Common pitfalls
•sorting by start time instead of finish time
•hand-waving the proof step
•forgetting that sort dominates runtime