Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Помогите решить следующую задачу: Есть множество интервалов. Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним. Подскажите в какую сторону гуглить/копать?
Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним.
Что-то я пока не вижу вопроса. Всё равно ведь придётся все остальные интервалы перебрать -- и что может быть быстрее?...
venco
Re: Интервалы
13.11.2010, 16:33
Быстрее вышеупомянутое interval tree.
Cave
Re: Интервалы
14.11.2010, 00:24
Если именно задан и он один, то быстрее перебора всех интервалов точно не получится. Если же набор интервалов фиксирован, а запросы разные, тогда да, дерево интервалов, оно же дерево отрезков.