A tutoring service has contracted you to work on pairing tutors with tutees. You

Question

A tutoring service has contracted you to work on pairing tutors with tutees. You are given a set of tutors U and a set of tutees V. Everyone has filled out some questionnaires, so you know which tutors are compatible with which tutees (i.e. able to tutor the right subject). Additionally, each tutor i has given a limit c_i on how many tutees they want to work with. Each tutee only gets one tutor. Describe an efficient algorithm for assigning tutors to tutees, such that as many tutees receive tutoring as possible. Give only the main idea.

Explanation / Answer

The scenario is like there has to be a N to 1 relationship between teachers(U) and tutees(V).
Our aim is to assign teachers to as many tutees as possible.
So, we need to satisfy maximum tutees with less possible teachers, so that we will reach our aim.
At the same time, though some teachers can do good at many tutees, but they have limit(Ci) on number of tutees, that they can handle.
And you know which teacher is good at which tutees. You have this report.

LIST = We should sort out tutees in non-decreasing order of the count, which tells number of teachers good at this tutee.Because following a order in assignment, will give good result than random assignment of tutee to teacher.

We will solve this problem like this below.
EXAMPLE:
   Raghu likes only Red shirts and Johnson likes both Red and Blue shirts. Raghu and Johnson can take only one shirt each. If you bought 2 shirts one is Red and another is Blue, to maximize shirts distribution, What you will do?
   Answer: We will give Red shirt to Raghu and Blue shirt to Johnson. Isn't it?(Think about it,why?)
   Here we are assigning shirt to the person who is having no choice or less choice, then we will process request for the person who is having next minimum number of choices.
  
   The same above happened will also apply here.

Now you can just assign the tutees, taken one by one from LIST from starting of LIST, to some teacher who is good at less number of tutees including this tutee and make sure that you should not exceed Ci limit of a teacher while assigning.This will enable us to left with teachers who are good at more number of tutees at each time.means if in case their Ci limit is also more, we can assign more tutees to them.
Note:If some teacher's Ci is more but he is not good at more number of tutees, then there is no much use.But if If some teacher's Ci is more and he is also good at more number of tutees, this scinario will be very much useful in achieving our aim,i.e to maximize assignment of tutees.

Follow above algorithm. You will left with maximum tutees are assiged to teachers.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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