В данной статье будет разобрана задача Promise Pool (Leetcode 2636)

Условие задачи

Дан массив асинхронных функций functions и максимальный размер пула n. Необходимо написать асинхронную функцию promisePool. Она должна возвращать Promise, который завершится, когда завершатся все функции из массива functions.

Размер пула определяет максимальное число Promise, которые могут одновременно выполняться. Функция promisePool должна начать выполнение максимально возможного количества функций из массива functions и брать новые функции на выполнение, когда какие-то из выполняющихся Promise завершаются. Функции необходимо выполнять в порядке их следования в массиве functions. Когда последний Promise перейдет в состояние resolved, promisePool также должен перейти в состояние resolved.

Например, если n = 1, promisePool должен выполнять по одной функции последовательно. Однако если n = 2, то сначала должны выполниться две первые функции. Когда любая из этих двух функций завершится, должна начать выполняться третья функция (если она есть в массиве) и так далее, пока не останется больше функций для выполнения.

По условию задачи, все функции из массива всегда успешно переходят в состояние resolved. Функция promisePool должна вернуть Promise, который завершается любым значением.

Пример

Входные данные:
functions = [
  () => new Promise(res => setTimeout(res, 300)),
  () => new Promise(res => setTimeout(res, 400)),
  () => new Promise(res => setTimeout(res, 200))
]
n = 2
Результат: [[300,400,500],500]
Объяснение:
Во входном массиве 3 функции. В них вызывается setTimeout на 300мс, 400мс, и 200mмс соответственно.
Они переходят в resolved в 300мс, 400мс, и 500мс соответственно. Результирующий promise завершается в 500мс.
В t=0, первые 2 функции начинают выполнение. Размер пула 2.
В t=300, 1-я функция завершает выполнение, а 3-я функция начинает. Размер пула 2.
В t=400, 2-я функция завершает выполнение. Больше функций в массиве functions не осталось. Размер пула 1.
В t=500, 3-я функция завершает выполнение. Размер пула 0, и результирующий promise также завершается.

Решение

Пусть i - индекс выполняемой в данный момент функции, availPool - число оставшихся ресурсов для выполнения Promise, completedCount - число завершенных Promise.

• В случае если массив функций пустой - мы можем завершить результирующий Promise.

• В ином случае, мы запускаем рекурсивную функцию executeNext, в которой:

  • Берем следующие k функций, где k равно числу доступных ресурсов.

  • Мы уменьшаем число свободных ресурсов availPool на k (availPool -= k) и запускаем k функций на выполнение.

  • По завершении каждой функции, мы освобождаем ресурс (availPool += 1) и увеличиваем на 1 число завешенных функций (completedCount += 1).

  • Если все функции завершились, мы завершаем итоговый promise, иначе - рекурсивно запускаем функцию executeNext.

var promisePool = function(functions, n) {
    let i = 0;

    let availPool = n;
    let completedCount = 0;

    return new Promise((resolve, reject) => {

        if(functions.length === 0){
            resolve();
            return;
        }

        const executeNext = () => {
            const pendingFunctions = functions.slice(i, i + availPool);
            i += pendingFunctions.length;
            availPool = 0;
            pendingFunctions.forEach(func => {
                func().then(() => {
                    availPool++;
                    completedCount++;
                    if(completedCount === functions.length){
                        resolve();
                    } else {
                        executeNext();
                    }
                })
            });
        }

        executeNext();
    });
};

/**
 * const sleep = (t) => new Promise(res => setTimeout(res, t));
 * promisePool([() => sleep(500), () => sleep(400)], 1)
 *   .then(console.log) // After 900ms
 */

Похожая задача мне встречалась на Контесте перед Two Day Offer от Yandex. Там задача была усложнена дополнительными деталями и видоизменена, но для ее решения было важно знать данную задачу (Promise Pool), а также быть знакомым с Heap / Priority Queue.