

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

There are two rooms (A and B) and $n$ people.

Each person i in $[1,n]$ supplies two non-negative numbers: $A_i$ and $B_i$, such that $A_i+B_i=n$.

The number $A_i$ can be interpreted as saying "I am willing to be in room A as long as there are at most $A_i$ people in it", and similarly $B_i$ for room B.

Now, we want to put $k$ people in room A, and $n-k$ people in room B, such that:

  • For each person $i$ in room A: $A_i \geq k$
  • For each person $j$ in room B: $B_j \geq n-k$

Is this always possible? If so, what is the way to find $k$?

Additionally, I will be happy to know if this question has a general name, or is a part of a general theory.


share|cite|improve this question
up vote 6 down vote accepted

A greedy approach will work. Take the person $i$ with the highest $A_i$, i.e. the most willing to go to A. If they fit in A, put them there; everyone else in A was at least as willing, so they're all still content. Continue until you reach a person who can't fit in A.

Now, you've put $k$ people in room A. Everyone remaining has $A_j \leq k$, and therefore $B_j \geq n-k$. Thankfully, there are only $n-k$ of them. So put them all in B, and we're done!

(Sorry, I'm not aware of a general theory.)

share|cite|improve this answer
Thank you! This solution seems to generalize to any number of rooms. – Erel Segal-Halevi Aug 8 '13 at 5:40
I often cite your answer in papers. Would you like to write it as an arXiv paper? This will make it more visible to other researchers who may need this algorithm. It will also be easier to cite, track citation count, etc. – Erel Segal-Halevi Nov 23 '15 at 6:48

Your Answer


