The following are the starting and ending times of activities A, B, C, D, E,…
2003
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: "asbscsaedsceesfsbedegseefehsgehe" Here, xs denotes the starting time and xe denotes the ending time of activity X. W 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 ?
- A.
3
- B.
4
- C.
5
- D.
6
Attempted by 91 students.
Show answer & explanation
Correct answer: B
Key idea: Scan the chronological events; increment the count on each activity start and decrement on each activity end. The maximum count reached is the minimum number of rooms required.
Start A: active = A (1)
Start B: active = A, B (2)
Start C: active = A, B, C (3)
End A: active = B, C (2)
Start D: active = B, C, D (3)
End C: active = B, D (2)
Start E: active = B, D, E (3)
Start F: active = B, D, E, F (4) <-- peak concurrency
End B: active = D, E, F (3)
End D: active = E, F (2)
Start G: active = E, F, G (3)
End E: active = F, G (2)
End F: active = G (1)
Start H: active = G, H (2)
End G: active = H (1)
End H: active = (0)
Conclusion: The maximum number of concurrent activities is 4, so the minimum number of rooms required is 4.