Suppose that n women check their coats at a concert : <p>I have a seemingly difficult algorithm that I must construct, and I'm not sure where to even start. Here it is:</p>

<p>Suppose that n women check their coats at a concert. However, at the end of the night,
the attendant has lost the claim checks and does not know which coat belongs to whom.
All of the women came dressed in black coats that were nearly identical, but of different
sizes. The attendant can have a woman try a coat, and find out whether the coat fits
(meaning it belongs to that woman), or the coat is too big, or the coat is too small.
However, the attendant cannot compare the sizes of two coats directly, or compare the
sizes of two women directly. Describe how the attendant can determine which coat
belongs to which woman in expected O(n log n) time. </p>

<p>I've thought of ways to do this, but none come close to O(n log n) time. 
Any help with this would be greatly appreciated.</p>
