First thing is to know the partitions of the number 5 (the team size you want to assembly). There are algorithms to generate the partitions of a number but since the number is small and fixed you don't need to worry about it. The partitions of 5 are: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1}, and {1,1,1,1,1}.
Make 5 lobby lists (L1,L2,L3,L4,L5). One for each lobby size. Each element will contain:
1) the lobby id
2) the time in queue
3) the sum of the ranks of the players that compose the lobby
L1 is the list of all lobbies of size 1, L2 is the list of all lobbies of size 2 and so on.
Now you make a list T of all possible teams of 5 people that you can assembly from the 5 lists of lobbies. To build that list you loop through the lists L1,...L5 according to the partitions of 5.
team {
int partition_type;
int lobby_index[5]; //each lobby_index value will mean a different thing depending on the value of partition_type
}
team_index = 0
//partition case 0: {5}
for (i5=0; i5<n5; i5++) do
//in the case of partition_type==0, only the first index is used and it is an index in the list of lobbies of size 5
Team[team_index++] = new team(partition_type = 0, lobby_index[0] = i5)
end
//partition case 1: {4,1}
for (i4=0; i4<n4; i4++) do
for (i1=0; i1<n1; i1++) do
//in the case of partition_type==1, the first index is an index in the list of lobbies of size 4 and the second is an index in the list of size 1
Team[team_index++] = new team(partition_type = 1, lobby_index[0] = i4, lobby_index[1] = i1)
end
end
//partition case 2: {3,2}
for (i3=0; i3<n3; i3++) do
for (i2=0; i2<n2; i2++) do
Team[team_index++] = new team(partition_type = 2, lobby_index[0] = i3, lobby_index[1] = i2)
end
end
//partition case 3: {3,1,1}
for (i3=0; i3<n3; i3++) do
for (i1a=0; i1a<n1-1; i1a++) do // 0 <= i1a < i1b < n1
for (i1b=i1a+1; i1b<n1; i1b++) do
Team[team_index++] = new team(partition_type = 3, lobby_index[0] = i3, lobby_index[1] = i1a, lobby_index[2] = i1b)
end
end
end
//partition case 4: {2,2,1)
for (i2a=0; i2a<n2-1; i2a++) do // 0 <= i2a < i2b < n2
for (i2b=i2a+1; i2b<n2; i2b++) do
for (i1=0; i1<n1; i1++) do
Team[team_index++] = new team(partition_type = 4, lobby_index[0] = i2a, lobby_index[1] = i2b, lobby_index[2] = i1)
end
end
end
//partition case 5: {2,1,1,1}
for (i2=0; i2<n2; i2++) do
for (i1a=0; i1a<n1-2; i1a++) do // 0 <= i1a < i1b < i1c < n1
for (i1b=i1a+1; i1b<n1-1; i1b++) do
for (i1c=i1b+1; i1c<n1; i1c++) do
Team[team_index++] = new team(partition_type = 5, lobby_index[0] = i2, lobby_index[1] = i1a, lobby_index[2] = i1b, lobby_index[3] = i1c)
end
end
end
end
//partition case 6: {1,1,1,1,1}
for (i1a=0; i1a<n1-4; i1a++) do // 0 <= i1a < i1b < i1c < i1d < n1
for (i1b=i1a+1; i1b<n1-3; i1b++) do
for (i1c=i1b+1; i1c<n1-2; i1c++) do
for (i1d=i1c+1; i1d<n1-1; i1d++) do
for (i1e=i1d+1; i1e<n1; i1e++) do
Team[team_index++] = new team(partition_type = 6, lobby_index[0] = i1a, lobby_index[1] = i1b, lobby_index[2] = i1c, lobby_index[3] = i1d, lobby_index[4] = i1e))
end
end
end
end
To calculate the rank of a Team[30] (just showing one case):
if Team[30].partition_type==2 then
i3 = Team[30].lobby_index[0]
i2 = Team[30].lobby_index[1]
rank = ( (L3[i3].rank) + (L2[i2].rank) ) / 5
end
Have 2 copies of T (or at least make sure you can traverse it in 2 different ways). One ordered by the average rank of that team and the other copy ordered by the average time in queue.
Now traverse the list T ordered by queue times from higher to lower. The first element is the one that has the priority to find a game first because their members are waiting for longer in average. Check the rank average of this team. Now use the rank value you found to determine all the teams that are +/- 1.5 from its rank. This is easily done by using the teams list T copy ordered by ranking. Now you just need to check if any of the teams in the rank range does not include any lobby of the current team (since one lobby can't be in both teams).
If there is such a team them you just found a game (if there are more than one pick then one with highest queue time). Remove all lobbies involved from their lists and recalculate all teams again. If not them get the next team in the list ordered by queue time and test again. Once you traverse all the queue time list you wait until the list of queues change and do all again.