Поиск как можно большего количества пар

Question

Я пытаюсь решить проблему, но, к сожалению, мое решение на самом деле не является лучшим для этой задачи.

Задача:

На вечеринке есть N гости (0 < < N 30000). Все гости рассказывают, когда они попадают на вечеринку и когда они уходят (например, [10; 12]). Задача состоит в том, чтобы фотографировать как можно больше людей на вечеринке. На фото может быть только 2 человека (пара), и каждый человек может быть только на одной фотографии. Конечно, фотография может быть сделана только тогда, когда оба участника на вечеринке. Это тот случай, когда интервалы их посещений перекрываются.

Моя идея: Я написал программу, которая из интервалов создает график соединений. На графике я ищу человека с наименьшим количеством соединений. От подключенных лиц я также выбираю человека с наименьшими связями. Затем эти два выбираются в виде пары на фотографии. Оба они удаляются из графика. Алгоритм выполняется до тех пор, пока соединения не останутся.

Этот подход работает, однако для вычисления программы существует ограничение в 10 секунд. С 1000 записей он работает через 2 секунды, но даже с 4000 требуется много времени. Кроме того, когда я пробовал его с 25000 данными, программа останавливается с ошибкой вне памяти, поэтому я не могу даже правильно сохранить подключения.

Я думаю, что здесь нужен новый подход, но я не мог найти другого способа сделать эту работу.

Может ли кто-нибудь помочь мне разобраться в правильном алгоритме для этой задачи?

спасибо!

Образец данных:

10 
1 100 
2 92 
3 83 
4 74 
5 65 
6 55 
7 44 
8 33 
9 22 
10 11 

Первая линия количество гостей дальнейшее данные интервалы людей на вечеринке.

Answer 1

Не нужно создавать график здесь, эта проблема может быть решена хорошо на структуре интервалов. Сортируйте людей по возрастанию их времени вылета (конечная точка интервала). Затем перебирайте их в этом упорядоченном порядке: если текущий человек не пересекается ни с кем, он должен быть удален. Если он пересекается с более чем одним человеком, возьмите в качестве пары одного из них, у которого есть самое раннее время выхода. Во время итерации вы должны сравнивать каждого человека только со следующими.

Доказательство этого подхода не так сложно, поэтому я надеюсь, что вы сможете доказать это сами. Что касается времени работы, то простым решением будет O (N^2), однако я думаю, что его можно свести к O (N * logN). В любом случае, O (N^2) поместится через 10 секунд на обычном ПК.

Answer 2

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

Итак, как фотограф, перейти к тому, чтобы быть первым человеком и ждать. Всякий раз, когда приходит человек, фотографируйте с ним и всеми другими лицами на вечеринке. Поскольку человек появляется только один раз, у вас не будет дубликатов.

Выполняя фото (например, итерируя по списку гостей), удалите тех гостей, которые фактически покинули вечеринку.

Answer 3

У меня есть очень простая идея:

Предполагает, партия будет принимать Xh, сделать X наборов для каждого часа, добавить к ним соответствующим людям. Конечно, люди, которые будут там дольше часа, будут в нескольких наборах. Теперь, если есть два набора «вместе» с четным числом ppl, вы можете взять n/2 фотографии для каждого набора. Если есть 2 набора нечетного числа людей, вы ищете кого-то, кто будет на каждом из этих 2-х наборов, и переместите его в один из них (так что у вас есть 2 четных набора людей, которые будут в одно и то же время на вечеринка).

Помните, что удалить все использованные ppl (см. Некоторые class - Man со списком всех его часов).

Моя идея, вероятно, должна быть расширена до более продвинутого алгоритма «движущихся людей» через более чем один соседний набор.

Answer 4

Похоже на классическую проблему maximum matching.

Вы строите график, в котором люди, которые могут быть изображены вместе (их интервалы времени пересекаются) связаны с краем, а затем найдите максимальное совпадение, например, с Edmond's Blossom algorithm.

Я бы не сказал, что его довольно легко реализовать. Тем не менее, вы можете получить довольно хорошее приближение к этому с Kuhn's algorithm для максимального соответствия в bipartite графики. Это действительно легко реализовать, но не даст вам точного решения.

Answer 5

Вы говорите, что у вас уже есть представление структуры графика. Я предполагаю, что ваши вершины представляют гостя и интервал их пребывания на вечеринке, а края представляют собой перекрытие соответствующих интервалов. То, что вам нужно решить, - это теоретический график maximum matching problem, который был решен ранее.

Однако, как указано в моих комментариях выше, я думаю, что вы можете использовать свойства проблемы, особенно транзитоподобные «если листья А до листьев B и листья B до появления C, то A и C не будут встречаться , либо «вот так:

Подождите, пока следующий, но еще не поставленный гость гость собирается уйти, а затем сделайте снимок этого с тем, кто уходит рядом с присутствующими.

Answer 6

Я думаю, что следующий может сделать:

Во-первых, прочитать все данные гостей и сортирует их в массив, оставляя время восходящие. Затем возьмите первый элемент массива и проведите по ним следующие элементы до тех пор, пока не будет найдено самое первое совпадение времени (время ожидания следующего гостя меньше времени удержания этого гостя), если он найден, удалите оба из массива как пару и сообщите об этом в другом месте , Если нет, удалите гостя, поскольку он не может быть спарен вообще. Повторяйте до тех пор, пока массив не будет пуст.

В худшем случае это также N^2, поскольку сторона может быть как [1,2],[3,4],..., где ни один из гостей не может быть соединен между собой, и алгоритм будет искать все 30000 гостей зря все время. Поэтому я не думаю, что это оптимальный алгоритм, но он должен дать точный ответ.