Походу никак... :)

у тебя там на 115 строке баг:

if (!ind>=0)

лишний "!"

в итоге условие всегда истинное, даже когда ind === -1. В этих случаях splice мгновенно, за O(1), удаляет последний элемент. Массив стремительно уменьшается, последующие итерации отрабатывают быстрее.

Если поправить баг, то всё норм.

для этого давным-давно придуманы самобалансирующиеся деревья. Красно-черное, АВЛ, и т.д.

И действительно.
Исправил.

Все зависит от работы с этим деревом. Когда мы говорим про O(log2N), то мы оцениваем количество операций сравнений при поиске в дереве. Когда работа - часто-часто ищем и иногда добавляем/удаляем, то все хорошо.
Когда работа - найти, если нашли удалить, если не нашли добавить - то самобалансировка будет происходить очень часто. А она тоже требует времени. А если сравнивать время на операцию сравнения, и время на балансировку, то не понятно сильно ли большим будет выигрыш.

voraa,
балансировка - накладные расходы, это да. Но она занимает по времени не более O(ln(n)), т.е. на больших объемах это всё равно копейки по сравнению с возможным растягиванием дерева и временем O(n).

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

а какая проверка делается в п.3? всей очереди, или только первого элемента?

и как извлекается первый элемента? как устроена очередь? если это просто массив с операцией shift, то может работать долго на длинной очереди.

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

Когда запрос приходит, можно быстро проверить по хэшмэпу обоих его участников и если свободны, сразу отправить в обработку. Зачем им кого-то ждать? Автор ничего не говорил про лимит одновременных обработок...

а вот кейс проверки всей очереди выглядит как узкое место, если очередь длинная. Здесь и надо как-то оптимизировать. Самое простое - сделать хэшмэп с очередями по каждому участнику. Освободилась пара [Вася, Петя], берем очереди по Васе и Пете и просматриваем их параллельно (в элементах очереди должен быть ещё таймстамп, когда добавили). В итоге мы найдем либо задачу снова [Вася, Петя], либо задачи [Вася, Х] и [Петя, Y], где X и Y отсутствуют в хэшмепе занятых. Вот эти задачи можно запускать в обработку, не забыв удалить элементы из персональных очередей для Вася, Петя, X и Y.
Худший случай - когда в этих очередях будет дохрена пар [Вася, А] и [Петя, Б], где А и Б - занятые. Что с этим делать, как их быстро поскипать, пока не совсем понятно.

про очередь в виде списка согласен. Можно добавить ещё пул элементов, чтобы их переиспользовать, не создавать каждый раз новые объекты.

Тут вопрос очередности. В какой момент мы берем только что пришедший запрос, и в какой момент из очереди.
Допустим косяком идут запросы со свободными, и вдруг появляются в очереди запросы, которые могут быть исполнены
Например освободились А и Б. Но в очереди есть А-Б и приходит запрос Б-А. Усложняется алгоритм выбора, какой запрос исполнять.
А поместив пришедший в очередь, и если просматривать всю очередь, а не только начальный, мы все равно выберем то, что может быть исполнено.

Пул свободных это ведь тоже список.
Нам не ведомо, что быстрее на js создание нового объекта (это какая то внутренняя достаточно быстрая операция) или помещение и извлечение объекта из списка. (это уже программа, с интерпретацией байткода, вызовы функций, что тоже не самая дешевая операция)