You have the answer this is standard Maximum bipartite matching problem. regards, Arun.
On Wed, May 28, 2008 at 7:26 AM, Zeratul <[EMAIL PROTECTED]> wrote: > > > > On May 28, 10:16 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > > On Wed, May 28, 2008 at 1:53 PM, Zeratul <[EMAIL PROTECTED]> wrote: > > > > > 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 ? > > > > Yes > > > > > > > > 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 ? > > > > Divide pins into two sets B, W according to their colors > A node in W with location <x1, y1> is connected to a node in B with > location <x2, y2> if and only if x1 > x2 and y1 > y2. > Then find a maximum bipartie matching between the two sets > > > > > > > > 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 > > > -- =================================== want to know more about me http"//ww.livejournal.com/users/arunachalam --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
