Для полноты я хотел бы добавить, что существует известная структура данных только для такой проблемы, известной (сюрприз, сюрприз) как дерево интервалов . Это в основном расширенное сбалансированное дерево (красный-черный, AVL, ваш выбор), в котором хранятся интервалы, отсортированные по их левой (нижней) конечной точке. Увеличение состоит в том, что каждый узел хранит наибольшую правую (высокую) конечную точку в своем поддереве. Это дерево позволяет вам найти все перекрывающиеся интервалы времени O (log n).
Это описано в CLRS 14.3.