Какой алгоритм использовать для поиска максимального пересечения множества отрезков?

Question

[isxaker]

Есть задача:

В музее регистрируется в течение дня время прихода и ухода каждого посетителя. Таким образом за день получены N пар значений, где первое значение в паре показывает время прихода посетителя и второе значения - время его ухода. Найти промежуток времени, в течение которого в музее одновременно находилось максимальное число посетителей.

Существует ли общеизвестный алгоритм для решения подобных задач?
Дерево отрезков для суммы подходит для решения этой задачи?

Answer 1

[Дмитрий Энтелис]

@isxaker Вы сами же предложили неплохой на мой взгляд вариант
stackoverflow.com/questions/2244964/finding-number...

В чем вопрос? :)

Comments

[isxaker]

@DmitriyEntelis у меня есть предположение, что эту задачу можно решить деревом отрезков для суммы. Вот хотел проверить свое предположение. qps.ru/Bd6ki

Answer 2

[meat]

раз не требуется точность, создаёте массив на 24*60 интеджеров, и каждым отрезком заполняете его прибавляя по единице к каждому элементу. потом проходитесь по полученному массиву, и находите максимум. O(n)

Comments

[isxaker]

@meat только получается в худшем случае мы будем заполнять массив за O(n*n)

[meat]

O(n*n) в каком это случае может получиться? n это количество записей а не записей или минут, и есть максимум количества минут. поэтому O(n*n) получится никак не может.

[meat]

на основе этой штуки ещё и график можно сделать

[isxaker]

@meat да, действительно. что-то я накосячил =)

Answer 3

[386DX]

Если не нужна идеальная точность, то можно день принять за 5* 228 минут(24 часа- ось x) и каждые пять минут проверять, сколько отрезков-посетителей в эти 5 минут входят. Потом из результатов искать максимум.

Comments

[isxaker]

скорее лучше вот так stackoverflow.com/questions/2244964/finding-number...

[386DX]

@isxaker со смешиванием всех значений начал думать, но решения сразу в уме не в увидел

[386DX]

@isxaker чтобы "increment numberOfCalls if time value marked as Start" я так понимаю нужен цикл, а значит проверять каждую секунду (или каждые пять минут, как я написал)

[isxaker]

цикл по значениям массива, который состоит из концов отрезков времени

[386DX]

@isxaker два человека зашли и вышли одновременно. Где там будет пересечение отрезков

[isxaker]

@386DX в тот момент пока они находились в библиотеке

[386DX]

@isxaker проехали

[isxaker]

можно считать с точностью до секунд например
важно ведь количество человек находящихся внутри музея