LINUX.ORG.RU

Интервалы, пересечения, объединения

 


0

2

Доброго всем дня!

Я тут перед отпуском туплю немного. И так у меня есть интервалы, которые поступают ко мне по очереди. Известно начало и конец. Интервалы могут пересекать друг друга и один может пересечь несколько. Если интервалы пересекаются, то их нужно объединить в один. Например уже есть A[0..100], B[200..300] и при получении С[50..250] остается один интервал [0..300].. Сейчас я это сделал линейно. то есть ищу по началу поступившего интервала куда его «воткнуть» и потом иду до конца, объединяя все попавшиеся.

Вообще вопрос в том, а какие есть алгоритмы на этот счет? интервалов может быть много и линейное решение, чую, не самое хорошее.

Спасибо.

Можно хранить интервалы в виде отсортированного списка и искать место, куда воткнуть, бинарным поиском.

sholom
()

можно сворачивать интервалы, используя SQL

bvn13 ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.