Как выбрать перекрывающиеся интервалы?

Question

[Roman Mindlin]

Есть база, состоящая из двух полей in_time и out_time (типа datetime).
Нужно отобрать пары записей, имеющие перекрывающиеся временные интервалы. Т.е. получить таблицу например:
common_in_time, common_out_time
В идеале, чтобы интервал был как можно более общим (т.е. если несколько записей имеют перекрывающиеся интервалы, то все они объединяются и common_in_time назначается самая ранняя дата in_time, а common_out_time - самая поздняя дата out_time)
Делаю с помощью SQLAlchemy для Flask, но вообще важна идея

Answer 1

[Rsa97]

В текущую таблицу добавляете поле-флаг для отметки просмотренных интервалов.
Создаёте вторую таблицу, куда будут писаться суммированные интервалы.
Дальше примерно так:
Выбираете первую немаркированную запись из таблицы, её границы используете как in и out.
Находите min_in и max_out всех записей, пересекающихся с текущей.
Eсли min_in != in или max_out != out, то in := min_in, out := max_out и повторяете предыдущий шаг.
Заносите полученный интервал в таблицу результатов.
Маркируете все записи в исходной таблице, пересекающиеся с полученной.
Повторяете алгоритм.

Answer 2

[Roman Mindlin]

Сам себе отвечу:

t2 = aliased(t1)
a = db.session.query(t1.in_time, t2.out_time).join(t2, 
            and_(t1.in_time < t2.in_time, t1.out_time > t2.in_time)).all()

t2 нужна, потому что SQLAlchemy не разрешает join с самим собой.