Разбор задачи про пересечение диапазонов дат с собеседования в телеком-компанию

Обнаружение пересечений в интервалах — довольно типичная задача, с которой приходится сталкиваться на практике. Зачастую это нужно для проверки данных на наличие ошибок.

Решение в лоб могло бы выглядеть следующим образом (см. рисунок 1). Я добавил поле id, чтобы разметить порядковый номер строки.

Но есть решение на основе оконки, которое покажет на порядок лучшие результаты с точки зрения производительности (см. рисунок 2). Оно базируется на том, что если в данных есть пересекающиеся интервалы, то существует как минимум два последовательных интервала I1 <= I2 (на основе порядка valid_from_dt, valid_to_dt, id), которые пересекаются.