Algorithm for creating a group based on free time
I'm trying to come up with an algorithm that will make groups based on the maximum free time available to a group of people in polynomial time, but I believe there might be an NP solution to this problem.
The problem is as follows:
We have divided the week into 1 hour intervals where users can apply for each slot whether they are free or busy. Let's say we collect this information from 30 users. Suppose also users% group_size = 0
Firstly:
Can these people be put into G-size groups so that each member in each G-size group has one overlapping free temporary space with each other?
Can these people be placed in G-size groups that lead to an optimal solution that has the maximum total overlap of free time slots among all groups?
For example, if we had a group of 6 people with the following free time:
A: from 13:00 to 23:00 on Sundays and from 13:00 to 15:00 on Monday.
B: from 14:00 to 23:00 on Sundays and from 13:00 to 15:00 on Monday.
C: from 13:00 to 23:00 on Sundays and from 19:00 to 19:00 on Monday.
D: 18:00 to 19:00 Sunday and 19:00 to 19:00 Monday.
E: from 17:00 to 19:00 Sunday and from 19:00 to 19:00 Monday
F: 6:00 pm to 7:00 pm Sunday and 1:00 pm to 3:00 pm Monday.
The algorithm would determine that A, B, F would be one group and C, D, E would be another group, since a maximum of two hours of free time overlaps between groups. This contradicts A, B, C and D, E, F, which only contains one overlapping time slot for each group member. As a result, this is the optimal solution, which is the largest match between all groups.
I realized that this problem is probably related to the Hopcroft-Karp algorithm, but it needs to be heavily modified to accomplish this task. Is their another algorithm that is more closely related to the solution than the Hopcroft-Karp algorithm? Can this solution be achieved in polynomial time?
Background:
We have a group of people (30-50) who want to volunteer for business, and they only have a certain amount of time when they are free during the week. We want to split them into groups of 3-5 and make them work together for this reason. We want the group members to have as much time with each other as possible, so we want to break them up into groups where they have similar free times.
Thanks a bunch and please let me know if this is an obvious question or if more clarification is needed.
source to share
At first glance, it looks like a given cover problem, where the subset is the number of faces separating the time interval, and the universal set is all faces.
U = {p0, p1, p2 ..... , p29} // Number of persons.
S = {S0, S1, S2, ....... S23} // number of 1 hour slots.
I'm still not sure how to use G (ideal group size).
source to share