@dachuan.huang

Great explanation.

Just wanted to elaborate the following line:

"If the new event collides with A, then it must collide with all events in the heap. So a new room must be created."

[Remember A is the interval that started not later than the new interval and finishes earlier than all other intervals in the heap.]

Because A is the interval that is furthest apart (among all the intervals in the heap) from the new interval. If the furthest apart interval has no gap with the new interval, the other intervals in the heap that less far apart from the new interval (than A) will not have gap either -- which would mean the new interval needs its own separate room.