Допустим, у меня есть таблица с двумя столбцами: start
и end
, оба целые числа, и таблица упорядочена по первому, затем второму столбцу. Каждая строка представляет собой интервал.
Мне нужна таблица объединенных интервалов: все перекрывающиеся или смежные интервалы слиты в один.
Его можно построить с помощью запроса JOIN, но он квадратичен по количеству строк, которое в моем случае составляет 4 миллиона строк (я решил составить этот вопрос, потому что запрос все еще выполняется).
Это также можно сделать за один проход, пропустив каждую строку и отслеживая максимальное время окончания - но как это сделать или что-то подобное в стандартном SQL? Есть ли какой-нибудь O (n) способ сделать это в SQL? Я использую SQLite прямо сейчас; на этот раз мне также поможет решение, специфичное для SQLite.
Из ответов на связанные вопросы ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ) Не могу сказать, возможно ли это.
Сможете?