I have been trying to solve this problem, that I got for last exam. Could not get a clue how to solve it. Pls give me some hint on how to solve in nlogn time.

Suppose you are given n red and n blue jugs all of different shapes and sizes. All
red jugs hold different amounts of water as do the blue ones. Moreover for every red jug,
there is a blue jug that holds the same amount of water, and vice versa.
The task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same
amount of water. To do so you may perform the following operation : pick a pair of jugs in
which one is red and one is blue, fill the red jug with water and then pour the water into the
blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if
they are of the same volume. Assume that such a comparison takes one time unit. Your goal is
to find an algorithm that makes a minimum number of comparisons to determine the
grouping. Remember that you may not directly compare two red jugs or two blue jugs.

>1. Prove a lower bound of Θ(n lg n) for the number of comparisons an algorithm solving
this problem must make.

>2. Give a randomized algorithm whose expected number of comparisons is O(n lg n)