Даны туалеты от 1 до n.Человек может сделать заказ в туалете и использовать его в течение определенного промежутка времени. Распределить туалеты для входящего бронирования в соответствии с приведенными ниже правилами.
- Назначить туалеты, которые находятся на максимальном расстоянии от другого туалета, используемого в настоящее время (пример: дляТуалет от 1 до 9, если 1 и 9 заняты, тогда выделите 5 для следующего запроса на резервирование.)
- Если для двух туалетов максимальная разница одинакова, тогда выделяйте больше всего слева, т.е. чей индекс меньше. (Пример для случая: 1до 9 туалетов, которые в настоящее время используются, составляют 1,9,5, затем для следующего резервирования выделяют 3)
Для данной входящей резервации и выходящей последовательности найдите сумму всех присвоенных серийных номеров туалета.
Ввод:
Первая строка T- Количество тестов (1 <= T <= 10) N количество туалетов, M запросов (1 <= N, M <= 20000) M строка следует за двумяцелое число A для типа запроса входящего / исходящего бронирования, B Person Id лица, сделавшего бронирование (если A == 1, то входящее резервирование, A == 2 после ухода из туалета) (1 <= A <= 2, 1 <= B <= 999999) </p>
Пример ввода: 1 5 7 1 1 1 2 1 3 1 4 2 1 1 1 1 5 Выход: 16 Объяснение: N = 5, M = 7. Идентификатор человека1 номер для туалета № 1, номер человека-2 для туалета № 5, номер человека 3 для туалета №.3, человек с номерами 4 до 2, затем человек с номером 1 вышел из туалета, затем человек с номером 1 снова сделал резервирование и назначил 1, и человеку с идентификатором 5 был присвоен 4. Таким образом, окончательный ответ: 1 + 5 + 3 + 2 + 1 + 4 = 16.
Мой подход к этой проблеме: создать максимальную кучу (startRange, endRange, Distance) и вывести максимальное значение расстояния из кучи.
if(startRange==1 || endRange==n) {
assignned accordingly
}else{
toilet no is avg = (startRange+endRange)/2
and pushed (startRange,avg-1,distance) and (avg+1,endRange,distance) into our heap
}
Теперь проблема в том, если некоторыевыходит из туалета, тогда как я могу обновить мою кучу, чтобы включить эти изменения.Или предложить любой другой алгоритм для решения этой проблемы.