I have to solve a simple meeting problem, but i cannot find the right keywords to find a correct mathematic description of the problem i'm trying to solve. Maybe someone can help me there:

The problem:

A number of participants have to meet with each other: Exemple: A have to meet with B and C (ABC) P have to meet with O and R (POR) A have to meet with D and P (ADP) X have to meet with Y and Z (XYZ) Z have to meet with O and I (ZOI) J have to meet with S and X (JSX)

The constraint is the following: two meetings are occuring at the same time. One person cannot attend two meeting at the same time.

I have to find a solution for scheduling the meetings: Week 1: ABC (Room 1) - POR (Room 2) Week 2: ADP (Room 1) - XYZ (Room 2) Week 3: ZOI (Room 1) - JSX (Room 2) Is a solution

Week 1: ABC (Room 1) - ADP (Room 2) This is impossible because A have to be at two meetings at the same time.

This exemple is fairly simple, but of course the number of meetings is a lot bigger in the case i waana solve, hence, trying to find an algorithm to solve it in a relevant time.

Can someone provide a reference to or an algorithm, or the name of the problem? Doesn't look like 'Maximum Bipartite Matching' or 'Bin packing'.

CodePudding user response：

Why do you think it isn't a maximum bipartite matching?

Let's say a node is a set of people who need to meet together. Draw an edge between every pair of nodes that are compatible (have no people in common).

In your example, nodes are:

0 ABC
1 POR
2 ADP
3 XYZ
4 ZOI
5 JSX

And edges are: (0,1), (0,3), (0,4), (0,5), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5).

Then the nodes at each end of each edge of a matching are compatible (can meet at the same time). A maximum matching will give you the max number of concurrent pairs of meetings, and if a solution is possible will include all nodes.