In 2006, the city of Beijing, China, instituted a policy that limits residents t

Question

In 2006, the city of Beijing, China, instituted a policy that limits residents to own at most one dog per household. Imagine you are running an online pet adoption website for the city. Your website contains pictures of adorable puppies that are available for adoption, and it allows for dogless Beijing residents to click on as many puppies as they like, with the understanding that they can adopt at most one. Suppose now that you have collected the puppy preferences from among n Beijing residents for your m puppies.

Describe an efficient algorithm for assigning puppies to residents that provides for the maximum number of puppy adoptions possible while satisfying the constraints that each resident will only adopt a puppy that he or she likes and that no resident can adopt more than one puppy

Explanation / Answer

Let Number of Puppies on portal which recieved atleast one like be P.

Similarily Number of residents having zero house pet and who needs a puppy be R.

Now we will be having a List of residents who liked a puppy p in P. So we will be having -

p1 = r1(number_puppy_liked), r2(number_puppy_liked) ......

So p1 is a puppy liked by resident r1 and r2. (number_puppy_liked) denotes the count of puppy liked by r1.

Algorithm is :

Step 1 - Sort puppies (p1,p2..) of set P in increasing order of likes recieved by residents.

Step 2 - If a puppy pn recieves only one like Allocate it to the corrosponding resident. Also Filter out this resident

from other puppies list.

Step 3 - Again sort the list since residents are removed and repeat step 2.

Step 4 - If there is no puppy left with single resident than allocate a puppy to a resident which has lowest number of likes count. For example - p = r1(2), r2(4) , In this case allocate puppy p to r1 as it has only 2 likes left. Since r1 is removed again remove r1 from puppies filter list and repeat step 3.

Step 5 - Keep repeating step 3 and step 4 till Residents count reaches to zero or number of puppies remaining reaches zero.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.