What is the best algorithm to match a student's schedule with a tutor's schedule?
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. 48
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. 48