Take the 2-minute tour ×

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|improve this question
add comment

1 Answer

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|improve this answer
Thank you! This solution seems to generalize to any number of rooms. –  Erel Segal Halevi Aug 8 '13 at 5:40
add comment

Your Answer


