I'm looking for an efficient way to assign n people to m rooms in a very specific way.
The program receives two sets of people (set of males and set of females), as well as a set of available rooms (rooms can have different sizes, ranging from 2 to 6).
The algorithm must assign people to the rooms in a way, that:
- A room can be only occupied either by all males, or by all females
- Noone can be alone
- The algorithm must minimize the number of occupied rooms
We can assume that there are at least 2 representatives of each gender.
The algorithm must return the assignment.
I've tried to do it, but all of the sollutions I come up with are at least O(n^3). Does anyone know an efficient way to do this?