Основной алгоритм
Я бы сортировал игроков по их рангу, так как высокопоставленные всегда отталкивали низкосортных. Затем вы начинаете с игрока с самым высоким рангом, даете ему то, о чем он просил (если он действительно самый высокий, он всегда выигрывает, поэтому вы также можете дать ему все, что он просил). Тогда я бы начал со второго по величине. Если он запросил что-то, уже взятое самой высокой, попытайтесь найти слот поблизости и назначьте этот слот ему. Теперь идет третий по величине. Если он попросит что-то, что уже было принято старшим, переместите его в слот поблизости. Если этот слот уже занят вторым по величине, переместите его в слот еще дальше. Продолжите со всеми другими игроками.
Некоторые настройки для рассмотрения:
Если несколько игроков могут иметь один и тот же ранг, вам может потребоваться реализовать некоторую «справедливость». Все игроки с одинаковым рангом будут иметь случайный порядок друг с другом, если вы сортируете их, например. используя QuickSort. Вы можете получить некоторую справедливость, если вы не делаете это игрок за игроком, но ранг за ранг. Вы начинаете с самого высокого ранга и первым игроком этого ранга. Обработайте его первый запрос. Однако перед обработкой его второго запроса обработайте первый запрос следующего игрока, имеющего наивысший ранг, а затем третьего игрока, имеющего наивысший ранг. Алгоритм такой же, как и выше, но при условии, что у вас есть 10 игроков, а игроки 1-4 имеют наивысший ранг, игроки 5-7 - низкие, а игроки 8-10 - очень низкие, и каждый игрок сделал 3 запроса, вы обрабатываете их как
Player 1 - Request 1
Player 2 - Request 1
Player 3 - Request 1
Player 4 - Request 1
Player 1 - Request 2
Player 2 - Request 2
:
Таким образом, у вас есть немного справедливости. Вы также можете выбирать случайным образом в классе ранжирования каждый раз, это также может обеспечить некоторую справедливость.
Вы можете реализовать справедливость даже в разных рядах. Например. если у вас 4 ранга, вы можете сказать
Rank 1 - 50%
Rank 2 - 25%
Rank 3 - 12,5%
Rank 4 - 6,25%
(Только примерные значения, вы можете использовать ключ, отличный от всегда умножения на 0,5, например, умножение на 0,8, что приводит к более медленному уменьшению чисел)
Теперь вы можете сказать, что вы начинаете обработку с Ранга 1, однако, как только 50% всех запросов Ранга 1 были выполнены, вы переходите к Уровню 2 и убедитесь, что 25% их запросов были выполнены, и так далее. Таким образом, даже пользователь с рангом 4 может победить пользователя с рангом 1, несколько победив первоначальный алгоритм, однако вы предлагаете некоторую справедливость. Даже игрок 4 ранга может иногда получить его запрос, он не «иссякнет». В противном случае игрок с рангом 1, планирующий каждый запрос в то же время, что и игрок с рангом 4, удостоверится, что у игрока с рангом 4 нет шансов когда-либо получить один запрос. Таким образом, есть хотя бы небольшой шанс, что он его получит.
После того, как вы убедились, что у каждого был обработан минимальный процент (и чем выше ранг, тем больше это), вы возвращаетесь к началу, снова начиная с 1-го ранга, и обрабатываете остальные свои запросы, затем остальные Запросы уровня 2 и т. Д.
Последнее, но не менее важное: Вы можете определить максимальное смещение слота. Если слот занят, приложение должно найти ближайший слот, который еще свободен. Однако что, если этот ближайший слот находится очень далеко? Если я запрашиваю слот в понедельник в 16:00 и приложение обнаружит, что следующим свободным будет среда в 9:00, это не очень полезно для меня, не так ли? У меня может не быть времени на среду вообще. Таким образом, вы можете ограничить поиск слотов тем же днем и сказать, что интервал может быть не более 3 часов. Если в этом диапазоне слот не найден, отмените запрос. В этом случае вам необходимо сообщить игроку: «Извините, но мы не смогли найти ближайший слот для вас; пожалуйста, запросите слот на другую дату / время, и мы посмотрим, сможем ли мы найти подходящий слот для вас».