On Wed, May 28, 2008 at 1:53 PM, Zeratul <[EMAIL PROTECTED]> wrote: > > On a board there are N * 2 pins colored with either black or white. > The number of black pins is equal to that of white ones. > > Each pin has a location <x, y>, and x y are all integers (there are no > more than one pins on the same location) > > We can pair a white pin located at <x1, y1> with a black pin located > at <x2, y2> if x1 > x2 and y2 > y2.
you mean y1 > y2 right ? > > > Now the problem is to find out the maximum number of pairs and print > them (any two pairs cannot contain the same pin). > > My idea is to first find all the pins that can make a pair, and do a > maximum bipartie matching. But it will cost O(N ^ 3) time. can you please explain how this will work ? > > > Is there any better solution for this problem? The hint says that a > greedy algorithm will be efficient. > > Sorry for my poor English. many thanks > > > -- Ciao, Ajinkya --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
