Как упорядочить очередь из разных групп?

Question

[Даниил]

К примеру есть сервис, который должен обслужить сотрудников. Сотрудники поделены на несколько групп с разным числом сотрудников. Нужно составить очередь так что бы все сотрудники обслуживались равномерно.
К примеру, есть 3 группы из группа А из 3, Б из 3, С и 6 сотрудников. Вывод должен быть таким A C Б C А C Б C А C Б C .

Comments

[Сергей Соколов]

Какой вывод должен быть, есть в Б не 3, а 4 элемента?

Answer 1

[Сергей Соколов]

Арифметика расставит элементы каждой группы отдельно на отрезке.

a   a   a
b   b   b
c c c c c c

Найти длину самой длинной группы. Делить её на длину очередной группы — получится шаг для группы.
Назначить каждому элементу свойством его положение на «отрезке».
Сложить все в один массив и отсортировать по этому положению.

Результат недетерменирован. Скажем, в этом примере на позиции 0 сразу три элемента: a, b и c. Какой из них будет на котором из трёх первых мест – ничем не определено.

реализация на JS

const groups = {
  A: ['a', 'a', 'a',],
  B: ['b', 'b', 'b', 'b',],
  C: ['c', 'c', 'c', 'c', 'c', 'c',],
};

const longest = Math.max.apply(null, Object.values(groups).map(a => a.length));
const sortMe = [];
for (let p in groups) {
  const values = groups[p];
  const step = longest / values.length; // 1 and bigger
  values.forEach((v, i) => sortMe.push({w: i * step, v: v}));
}

sortMe.sort((a, b) => a.w - b.w);

const result = sortMe.map(el => el.v);

console.log(result);
// ["a", "b", "c", "c", "b", "a", "c", "b", "c", "a", "c", "b", "c"]

Comments

[Даниил]

спасибо, но как быть с таким случаем, одна группа из 100 элементов, и еще 100 групп по 1 элементу.
Еще к примеру думал о создании массива для всех элементов, и потом его помешать случайным образом, в принципе результат должен быть близок к требуемому, но хочется найти наиболее производительный алгоритм. .

[Сергей Соколов]

Даниил, если хочется оптимальной для каждого случая расстановки элементов – то задача становится больше похожей на оптимальную упаковку (упаковку рюкзака). В примере с 100 и 100 интуитивно понятно, что 100 одиночек должны быть каждый по 1 между двумя из сотни. Это следует из нового требования «равномерности»: минимизации вариативности расстояния между элементами одной группы после сериализации. Т.е. что первая сотня должна идти как можно более «ритмично».
Контрпример для усложнения тут взаимно простые числа длин серий. Например 3,5,7,11. Как их расставить?

[Сергей Соколов]

Может, по-другому чуть. Число всех вообще элементов – это число тиков, на которые делится отрезок.
Для каждого тика прописать желающих в него попасть. Но с разными приоритетами. Для 100-100 будет 200 отрезков. На первый попадает А и сто единичных. Но у А приоритет высокий: ему надо попасть на этот или на следующий железно. А у каждого из единичных приоритет низкий: им годится вообще любой из 200.
Так получится, в первую попадёт А, во вторую один из единичных. В третью, следующий А (опять высокий приоритет), в 4 один из единичных. И т.д.

Answer 2

[Wataru]

Делайте жадно. Ставьте в очередь сотрудника той группы, которая меньше всего загружена пока.

Изначально у всех загрузка на 0/k[i] - поэтому выбираем любую случайно или первую по порядку.
Допустим выбрали группу a. Поставили одного сотрудника. У этой группы загрузка стала 1/k[0]. Это больше 0/k[i] для всех остальных групп, поэтому следующим сотрудником вы поставите кого-то другого.

Можно делать тупо - двумя циклами (внешний по общему количеству сотрудников, внутренний по всем группам).
Можно ускорить процесс, если использовать приоритетную очередь на минимум. Изначально кладете в очередь все группы с приоритетами 0. Потом достаете оттуда минимум, сотрудника этой группы ставите на заказ и добавляете в очередь эту группу назад с приоритетом +1/k[i]. Можно не класть в очередь группы, в которых не осталось незадействованных сотрудников. И тогда остановка - когда очередь пуста. Можно просто останавливаться когда у минимальной в очереди группы приоритет (k[i]/k[i]).