What is the best algorithm to match a student's schedule with a tutor's schedule?

Question

I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, locations). Now, I am getting stuck at the most difficult one which is freetime matching.

The student's sample freetime:

Monday: 7AM-8:30AM
Wednesday: 6AM-8AM
Friday: 9AM-10:30AM

Now I want to match this student with a list of tutors who have the freetime that can match with the student's freetime. In addition, each session between a student and a tutor must be 90 minutes.

For example, the following is the tutor's freetime:

Monday: 6AM-9AM => matches because both the student and tutor can start their session at 7AM, and when the session ends at 8:30AM, it is still in the range of the student's freetime and tutor's freetime.
Tuesday: 7AM-10AM => doesn't match, of course.
Wednesday: 7AM-9AM => doesn't match because both of them can start their session at 7AM, but when the session ends 8:30AM, the student's time is already over.
Friday: 10AM-11:30AM => matches, like the case in Monday.
=> Conclusion: this tutor doesn't match with the student since he just matches 2 out of 3 days with the student (Monday and Friday)

I tried to use Hash data structure to solve the problem.

student_freetime = { monday: { start_time: 7, end_time: 8.5 }, wednesday: { start_time: 6, end_time: 8 }, friday: { start_time: 9, end_time: 10.5 } }

tutor_freetime = { monday: { start_time: 6, end_time: 9 }, tuesday: { start_time: 7, end_time: 10 }, wednesday: { start_time: 7, end_time: 9 }, friday: { start_time: 10, end_time: 11.5 } }

However, I think this is a bad solution since I need to use loop and if many times.

Therefore, I have been searching for the best solution for this problem, and found some suggestions on using the Hopcroft–Karp algorithm on stackoverflow. However, I've never implemented graph related algorithm before, so I am not sure the Hopcroft–Karp algorithm is the best choice in my case. As I understand, to implement Hopcroft–Karp algorithm first I need to create to have 2 sets of data. In this case, I think the first set would be the student's freetime in a particular day, and the second set would be the tutor's freetime in the same day. But at this step, I am wondering how can I match their time by using Hopcroft–Karp algorithm as I pointed out above, their freetime can be different and still match as long as it satisfies the session's limit time (90 minutes). I would be appreciated if anybody could give me some suggestions here or point me to the right resources/similar problems.

Answer 1

This sounds like an instance of the assignment problem (see also our tag). You can also view it as a bipartite matching problem. There are standard algorithms for these problems; I suggest you use one of them. Hopcroft-Karp is one of those standard algorithms. I suggest that you either look for an existing implementation of one of those algorithms, or study them and implement themselves.

Expressing this as a network flow algorithm or as an instance of linear programming might provide extra flexibility to deal with additional constraints.

The specifics of how to express your problem as an instance of these problems will depend on the specific constraints you want to impose (e.g., is there a limit on the number of students you want to assign each tutor to? is it ok to limit things to a set of non-overlapping 90-minute time slots?), which you haven't specified in the question, so it's hard for us to say much more.

I suggest you try applying one of those approaches to your specific problem, study one of the standard algorithms, and if you get stuck understanding some specific aspect of the problem, ask a new question where you ask about that specific difficulty.