The following are the starting and ending times of activities and respectively in chronological order: . Here, denotes the starting time and denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
View worked solution
Answer: B
This problem is a classic instance of the Interval Partitioning (or Room Scheduling) problem. The minimum number of rooms required to schedule all activities is equal to the maximum number of overlapping activities at any single point in time.
We can find this by simulating the timeline chronologically and tracking the set of active activities at each step:
| Event | Action | Active Activities | Room Count |
|---|---|---|---|
| Start | 1 | ||
| Start | 2 | ||
| Start | 3 | ||
| End | 2 | ||
| Start | 3 | ||
| End | 2 | ||
| Start | 3 | ||
| Start | 4 (Max) | ||
| End | 3 | ||
| End | 2 | ||
| Start | 3 | ||
| End | 2 | ||
| End | 1 | ||
| Start | 2 | ||
| End | 1 | ||
| End | 0 |
The maximum number of concurrent activities is (which occurs when activity starts while and are still running). Thus, the minimum number of rooms required is .
Free practice · Your answers on this page are not saved.