Quiz 6
CS F364: Design & Analysis of Algorithms
Quiz 6 — June 16, 2026
Coverage: Greedy Algorithms
Note
Instructions:
- Time: 15 minutes.
- Write your answers clearly on paper, scan, and upload to Google Classroom.
- Show all steps for full credit.
Question: Interval Scheduling — Multiple Rooms
You are scheduling the following intervals in a venue with multiple identical rooms. Every interval must be scheduled in some room, and no two intervals in the same room may overlap. You want to use the minimum number of rooms.
| Interval | \(I_1\) | \(I_2\) | \(I_3\) | \(I_4\) | \(I_5\) | \(I_6\) |
|---|---|---|---|---|---|---|
| Start | 1 | 2 | 3 | 5 | 6 | 7 |
| Finish | 5 | 4 | 6 | 7 | 8 | 9 |
Describe the greedy algorithm for this problem (sorting rule and assignment rule). Run it step-by-step on the given intervals, showing which room each interval is assigned to. State the total number of rooms needed and explain why it is optimal.