Я отвечаю, потому что предыдущие ответы явно ломаются в тех случаях, когда многие люди выбирают один и тот же слот, а у многих слотов нет или мало выбора.Например, если все пользователи выберут слоты (1,2,3) в этом порядке, топологическая сортировка не поможет.
В идеальной ситуации каждый человек выберет один слот, и все слоты будут иметьтакое же количество выбирающих (+/- 1).Если бы я сам решал эту проблему, я бы попробовал режим «первым пришел - первым обслужен» с онлайн-сервером в реальном времени, чтобы люди могли выбирать только из тех слотов, которые остаются открытыми во время входа в систему.
Если онлайн первым пришел, первым обслужен неосуществимо, я бы использовал метод, который мотивирует людей выбирать разные слоты, возможно, с элементом случайности.Вот один из таких методов:
Пусть всего будет U человек, борющихся за H временных интервалов.(H = 22.) Предположим, что каждому человеку назначен ровно один слот.Пусть P = [U / H] (то есть U / H, усеченное до целого числа) будет номинальным числом людей на слот.(В слотах U mod H будет P + 1 человек.) Для слота j пусть D_j будет 3 * R1j + 2 * R2j + 1 * R3j, где Rij - количество раз, когда слот j запрашивается в качестве выбора i.D_j выше для более желательных слотов.Дайте каждому пользователю k баллов W_k = 1 / D_ {C1k} + 2 / D_ {C2k} + 3 / D_ {C3k}, где Cik - это i-й выбор пользователя k.То есть пользователь получает больше очков за выбор слотов с низкими значениями D, а выбор 2-го или 3-го выбора взвешивается больше, чем выбор 1-го выбора.
Теперь сортируйте слоты в порядке возрастания по D_j.(«Самые загруженные» слоты будут заполнены первыми.) Сортируйте пользователей по убыванию W_k по убыванию и назовите этот список S.
Затем для каждого слота j: пока j не заполнен, {Найти сначалачеловек k в S, который выбрал слот j в качестве выбора 1;если найдено, переместите k из S в слот j.Если ничего не найдено, найдите первого человека k в S, который выбрал слот j в качестве выбора 2;если найдено, переместите k из S в слот j.Если ничего не найдено, найдите первого человека k в S, который выбрал слот j в качестве выбора 3;если найдено, переместите k из S в слот j.Если ничего не найдено, добавьте последнего человека k из S в слот j и удалите k из S.}
В упомянутом ранее плохом случае, когда все пользователи выбирают слоты (1,2,3) по порядку,этот метод назначит случайные группы людей всем слотам.Учитывая постановку задачи, это так же хорошо, как и следовало ожидать.
Обновление 1: Полное заполнение самых загруженных слотов в первую очередь может привести к тому, что некоторые люди окажутся в своих избранных местах второго или третьего выбора, когда они могли быпомещены без конфликта в их местах первого выбора.Есть плюсы и минусы в заполнении наиболее загруженных, которые может решить теоретико-игровой анализ.В отсутствие этого анализа мне кажется, что лучше заполнить его следующим (более простым) методом: как и прежде, создайте отсортированный список пользователей S в порядке убывания по W_k.Теперь просмотрите список S по порядку, поместив людей в первый доступный слот, который они выбрали и вписали, а затем в самый популярный слот, который все еще имеет отверстие.Например, если пользователь k выбрал слоты p, q, r, поместите k в p, если p имеет место, иначе q, если q имеет место, иначе r, если r имеет место, иначе j, где j находится среди слотов с отверстиями, а D_j является наибольшим.
Этот подход легче объяснить пользователям, он немного проще для программирования и в целом может приблизиться к оптимальному.В тех случаях, когда слоты можно заполнять, не прибегая к третьему месту, это будет сделано.