D
D
Daniel2021-01-16 21:12:20
Algorithms
Daniel, 2021-01-16 21:12:20

How to order a queue from different groups?

For example, there is a service that should serve employees. Employees are divided into several groups with different numbers of employees. It is necessary to make a queue so that all employees are served evenly.
For example, there are 3 groups of group A of 3, B of 3, C and 6 employees. The output should be A C B C A C B C A C B C .

Answer the question

In order to leave comments, you need to log in

2 answer(s)
S
Sergey Sokolov, 2021-01-16
@sergiks

Arithmetic will arrange the elements of each group separately on the segment.

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

Find the length of the longest group. Divide it by the length of the next group - you get a step for the group.
Assign each element a property to its position on the "segment".
Put everything into one array and sort by that position.
The result is non-deterministic. Let's say in this example there are three elements at position 0 at once: a, b and c. Which of them will take which of the first three places is not defined by anything.
implementation in 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"]

W
Wataru, 2021-01-16
@wataru

Do it greedily. Queue the employee of the group that is least loaded so far.
Initially, everyone has a load on 0/k[i] - therefore, we choose any randomly or the first in order.
Let's say we chose group a. One employee was assigned. This group has a load of 1/k[0]. This is more than 0/k[i] for all other groups, so you will put someone else as the next employee.
You can do it stupidly - in two cycles (external for the total number of employees, internal for all groups).
You can speed up the process if you use the priority queue at a minimum. Initially, you queue all groups with priority 0. Then you take out a minimum from there, put an employee of this group on order and add this group back to the queue with a priority of +1/k[i]. You can choose not to queue groups that do not have unused employees. And then stop - when the queue is empty. You can just stop when the minimum group in the queue has priority (k[i]/k[i]).

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question