2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Интервалы
Сообщение12.11.2010, 19:58 
Помогите решить следующую задачу:
Есть множество интервалов. Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним. Подскажите в какую сторону гуглить/копать?

 
 
 
 Re: Интервалы
Сообщение12.11.2010, 20:13 
Аватара пользователя
Дерево интервалов?

 
 
 
 Re: Интервалы
Сообщение13.11.2010, 11:53 
Iliya в сообщении #374200 писал(а):
Нужно максимально быстро определять для заданного интервала [a,b] количество пересекающихся с ним.

Что-то я пока не вижу вопроса. Всё равно ведь придётся все остальные интервалы перебрать -- и что может быть быстрее?...

 
 
 
 Re: Интервалы
Сообщение13.11.2010, 16:33 
Быстрее вышеупомянутое interval tree.

 
 
 
 Re: Интервалы
Сообщение14.11.2010, 00:24 
Если $[a;b]$ именно задан и он один, то быстрее перебора всех интервалов точно не получится.
Если же набор интервалов фиксирован, а запросы разные, тогда да, дерево интервалов, оно же дерево отрезков.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group