Преобразовать список сессий во временной ряд

Есть сырые данные истории использования объектов в виде списка сесстй-троек (id объекта, время начала, время окончания) [(1, "2012-09-20 00:00:00+04", "2012-09-20 05:00:00+04"), (1, "2012-09-20 07:30:00+04", "2012-09-20 09:25:00+04"), (2, "2012-09-20 07:00:00+04", "2012-09-20 09:15:00+04")] Т.е., в данном примере объект 1 использовался дважды, с 00:00 по 05:00 и с 07:30 по 09:25, а объект 2 — с 07:00 по 09:15. Список сейчас отсортирован по ID объекта и потом по возрастающему времени, но можно подать данные в любом виде — в общем-то, это таблица в SQL'ной RDBMS. Записи как правило, не должны, но, теоретически, могут пересекаться — т.е., может случиться так, что будет [(1, "…", "… 12:00:37"), (1, "… 11:59:42", "…")], и в этом случае можно считать, что использование в районе 12 часов не прерывалось. Хочу получить из такого списка временной ряд, условно, следующего вида: [("2012-09-20 00:00:00+04", {1}), ("2012-09-20 05:00:00+04", {}), ("2012-09-20 07:00:00+04", {2}), ("2012-09-20 07:30:00+04", {1,2}), ("2012-09-20 09:15:00+04", {1}), ("2012-09-20 09:25:00+04", {})] Т.е. с 00:00 (минимальная дата-время в истории) использовался объект 1, потом в 05:00 ничего, потом с 07:00 — объект 2, затем оба объекта, и т.д., до 09:25, на которое данные закончились. Подскажите, пожалуйста, хороший алгоритм и структуры данных для быстрого выполнения такого преобразования. Объемы — до 10000 объектов, за сроки различной продолжительности (сутки, неделя, месяц, 3 месяца, 6 месяцев, год, больше не интересно), до 100000 записей в сутки. Процессорного времени жалко, памяти — сколько угодно, в физически разумных пределах. Очевидный «жадный» алгоритм с пробегом по временному интервалу не годится — алгоритм не должен напрямую зависеть от продолжительности рассматриваемого интервала, только от количества записей в истории.

Ответ

В такой формулировке, если я правильно все интерпретировал, то звучит как типичный use case для структуры данных под названием Interval Tree. Алгоритм может выглядеть примерно следующим образом:


Нестрогое обоснование и оценка сложности алгоритма:
Понятно, что изменение множества текущих выполняемых объектов может произойти только в момент start или end для некоторой тройки, поэтому подход с UNIQUE должен сработать. Время работы для n входных элементов будет равно O(n log n) + O(n) + O(n * (log n + k)) = O(n * (log n + k)), где k - это количество элементов с пересекающимися интервалами, поскольку сложность вставки составляет O(log n), а стоимость запроса - O(log n + k) Алгоритмическую сложность операций для Interval Tree я подсмотрел здесь.
В свое время пользовался boost::icl для схожих целей.