Quiz 6 (Solutions)
CS F364: Design & Analysis of Algorithms
Quiz 6 — June 16, 2026
Coverage: Greedy Algorithms
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.
Solution
Greedy algorithm: Sort intervals by start time (earliest first). For each interval in order, assign it to any existing room whose last scheduled interval has finished before this interval starts; if no such room exists, open a new room.
Step-by-step trace:
| Step | Interval | Room | Rooms and their finish times |
|---|---|---|---|
| 1 | \(I_1\) [1,5] | Room 1 | R1: 5 |
| 2 | \(I_2\) [2,4] | Room 2 | R1: 5, R2: 4 |
| 3 | \(I_3\) [3,6] | Room 3 | R1: 5, R2: 4, R3: 6 |
| 4 | \(I_4\) [5,7] | Room 1 | R1: 7, R2: 4, R3: 6 |
| 5 | \(I_5\) [6,8] | Room 2 | R1: 7, R2: 8, R3: 6 |
| 6 | \(I_6\) [7,9] | Room 3 | R1: 7, R2: 8, R3: 9 |
Total rooms needed: 3
Why optimal: At time interval [3,4], three intervals (\(I_1\), \(I_2\), \(I_3\)) are all active simultaneously. Any single room can hold at most one interval at a time, so at least 3 rooms are necessary. The greedy algorithm achieves exactly this lower bound, hence it is optimal.