# Assign n people to m rooms of different sizes, such that noone is alone

I'm looking for an efficient way to assign n people to m rooms in a very specific way.

INPUT:

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).

ASSIGNMENT CONDITIONS:

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.

OUTPUT:

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?

• Can you post your $O(n^3)$ algorithm? There's an easy $O(n)$ algorithm for the single-gender case, but it's driving me up the wall trying to figure out even a subexponential algorithm that provably always works for the two-genders case. – Aaron Rotenberg Dec 7 '19 at 5:07
• The best algorithm I have at this point is around $O(n^{10})$, by dynamic programming on the state vector $(p_2, ..., p_6, q_1, ..., q_5, n_m)$, where $p_k$ is the number of empty rooms with $k$ seats, $q_k$ is the number of male-occupied rooms with $k$ remaining seats, and $n_m$ is the number of unassigned males. It's almost like a more complicated change-making/Frobenius number problem. – Aaron Rotenberg Dec 7 '19 at 15:47
• In the future, when you receive feedback, requests for clarification, suggestions for improvement, please edit the question to incorporate that into the question. Don't leave comments with clarifications -- edit the question. We want people to be able to understand what is being asked, without having to read the comments. I made that change for you this time so you can see an example of what I have in the mind. In the future, I encourage you to do it proactively yourself -- I think it might make it more likely you get helpful answers. Thank you! – D.W. Dec 7 '19 at 21:51
• A moderator deleted my answer to the original question. That's quite annoying, since it only needed some minor modifications. So I suppose it will have to go without an answer. @D.W. : Very annoyed. – gnasher729 Dec 7 '19 at 22:52
• @gnasher729, as I understand it, your answer does not match the question -- see my edits to the question, specifically the constraint "A room can be only occupied either by all males, or by all females", which based on a comment from the original poster appears to be what they meant. If you think I have misunderstood your answer, I can certainly undelete it. Would you like me to do that? – D.W. Dec 7 '19 at 22:56