### Water Jug Problem

Source: Introduction to Algorithms (by Cormen, Rivest, Leiserson) Problem: Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. How can you find the grouping of the jugs into pairs of red and blue jugs that hold the same amount of water, in the minimum number of comparisons. The only operations allowed is compare between a red and a blue jar (no two reds, no two blues) Update (Dec 30, 2010): Problem statement changed a bit to make it more understandable. Solution: Posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) and Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments! Explained in detail by me in comments!