Question:Say you're given a class schedule. Each of the classes you want to take has two sections at different time blocks. No time blocks overlap. You want to select a section from each class so that none of the selected sections overlap. How can you model this as a problem we've seen in class?
Answer: Include a node in the graph for each time block and include a node for each section. Draw an edge between a time-block node and a section-node if the section meets in that time block. The problem is equivalent to finding the minimum matching that we solved using ``augmenting paths''.
+--- 8:30- 9:20 ---- 15-211 ----+
| / |
| 9:30-10:20 ---- 21-147 -- |
| / X \ |
start- 10:30-11:20 ---- 21-240 -- end
| \ \ / |
| 11:30-12:20 ---- 18-299 -- |
| \ |
+---12:30- 1:20 ---- 15-299 ----+