Блог

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

 Person  TimeSlot
1       1
1       2
1       3
2       2
3       1
3       2
4       2
 

Идеальным результатом, основанным на данных, был бы один временной интервал для каждого человека, основанный на их предпочтениях выше. Давайте также скажем, что в случае Person 2 и Person 4, у которых есть только доступный временной интервал 2, Person 2 получает предпочтение, поскольку они отправили свой ответ ранее (номера пользователей присваиваются в порядке отправки времени):

 Person  TimeSlot
1       3
2       2
3       1
4       N/A
 

Только у меня гораздо больше людей и временных интервалов. Временных интервалов больше, чем людей. Любая помощь по этому вопросу будет высоко оценена. Сначала я пытался перебирать каждого человека, назначая первый выбранный ими слот. Но я столкнулся с проблемой, когда, например, человеку 1 был назначен временной интервал 1, человеку 2 назначен временной интервал 2, но человеку 3 не удалось назначить время, поскольку были приняты оба их предпочтения.

Вводит: максимальное сопряжение

К счастью для вас, проблема довольно хорошо изучена, и многие библиотеки уже реализуют этот алгоритм. Например, networkx. Просто постройте график и используйте функцию в соответствии с документацией.
В вашем случае вы пытаетесь найти максимальное сопряжение person ~ time_slot в двудольном графе с ребрами, ведущими от person к каждому временному интервалу, который он отметил.

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

Или, если вы хотите пофантазировать, сетевые потоки также могут решить вашу проблему. Сеть — Источник — люди — временные интервалы — приемник, и максимальный поток находит пары.