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. 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. 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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
