Шаг 1

Частая задача, которую решают очереди — это симуляция каких-либо процессов. Обычно в рамках таких симуляций у нас есть какая-то система, на состояние которой мы как раз и симулируем влияние. А очередь обычно представляет собой набор данных, которые на эту систему влияют. В качестве примера давайте посмотрим на следующую задачу симуляции. Есть общие серверы для произведения вычислений на видеокартах, и обычно они полностью заняты. Чтобы не предлагать пользователям, которые хотят туда попасть, просто сделать это когда-то позднее, администраторы ввели очередь. Теперь каждый человек знает, сколько людей ему нужно пропустить вперёд, чтобы зайти на сервер. Серверы знают, сколько на них установлено доступных видеокарт и сколько в среднем каждый человек из очереди пользуется ими. Напишите функцию, которая будет прогнозировать для вставшего в очередь пользователя, сколько ему придётся прождать. Для упрощения будем считать, что первый человек в нашей симуляции зайдёт на сервер сразу же, как только займёт очередь. В этой задаче системой, на которую мы будем «влиять» является сервер, а данными, которые это делают, будут люди из очереди. В этой задаче данные из очереди не порождают данные в конец очереди. А очередь уже заранее определена: нам не нужно определять её из других данных (в отличие, например, от поиска в ширину, который мы недавно вспоминали).

import {test} from "./tester";

/*
Задача: смоделировать очередь людей (queue) на сервер из slots видеокарт
*/

function predict(queue, slots) {
  return 0;
}

test(predict([1, 2, 3], 1), 6);
test(predict([1, 2, 3], 2), 2);
test(predict([1, 2, 3], 3), 1);
test(predict([3, 2, 3], 3), 2);

Шаг 2

С системой и данными определились. Теперь нам нужно лишь понять, как именно данные будут влиять на систему. В нашем случае мы будем искать видеокарту с наименьшей занятостью: ту, которая будет занята меньшее количество времени. И симулировать, что следующий человек стоит в очереди на неё и занимает видеокарту столько времени, сколько ему нужно, а затем уходит и освобождает для следующего человека из очереди.

import {test} from "./tester";

/*
Задача: смоделировать очередь людей (queue) на сервер из slots видеокарт
*/

function predict(queue, slots) {
  // карты, установленные на сервере, на них мы будем влиять очередью
  const cards = Array(slots).fill(0);

  // пока в очереди есть необслуженные данные
  while (queue.length) {
    // обрабатываем их
    const current = queue.shift();
  }

  // а вернуть нам нужно минимальное время, через которое освободится хотя бы одна видеокарта
  return Math.min(...cards);
}

test(predict([1, 2, 3], 1), 6);
test(predict([1, 2, 3], 2), 2);
test(predict([1, 2, 3], 3), 1);
test(predict([3, 2, 3], 3), 2);

Шаг 3

Для этого напишем небольшую функцию, которая будет искать наименее занятую карту и станем складывать её текущую занятость с прогнозируемой занятостью от человека из очереди. Всё, наша простенькая симуляция готова!

import {test} from "./tester";

/*
Задача: смоделировать очередь людей (queue) на сервер из slots видеокарт
*/

function findMinIndex(machines) {
  const min = Math.min(...machines);

  return machines.indexOf(min);
}

function predict(queue, slots) {
  // карты, установленные на сервере, на них мы будем влиять очередью
  const cards = Array(slots).fill(0);

  // пока в очереди есть необслуженные данные
  while (queue.length) {
    // обрабатываем их
    const current = queue.shift();

    const minIndex = findMinIndex(cards);

    cards[minIndex] += current;
  }

  // а вернуть нам нужно минимальное время, через которое освободится хотя бы одна видеокарта
  return Math.min(...cards);
}

test(predict([1, 2, 3], 1), 6);
test(predict([1, 2, 3], 2), 2);
test(predict([1, 2, 3], 3), 1);
test(predict([3, 2, 3], 3), 2);
test(predict([4, 5, 3, 3], 2), 7);

File tester.js

const results = document.getElementById('results')

export function test(left, right) {
  const result = document.createElement('li');

  if (left === right) {
    result.innerHTML = "Тест пройден!";
    result.style.color = "green";
  } else {
    result.innerHTML = `Тест не пройден! ${left} не равно ${right}`;
    result.style.color = "red";
  }

  results.appendChild(result);
}