Geek Answers Handbook

Meeting scheduling algorithm with overlap times

I want to do something similar to an appointment scheduling algorithm (N people with N free slots, satisfaction with requirements). using the Hopcroft-Karp algorithm. But my additional requirement is that my time intervals overlap. For example. Time intervals can be from 10 to 11 am or 10.15 am to 11.15 am. Therefore, if I choose 10am to 11 am slot, I do not want to choose 10.15 in the morning until 11.15 in the morning. Is it possible to achieve this without hitting the performance?

+7
algorithm matching graph graph-algorithm constraint-programming
source share
1 answer

You can use a stream algorithm similar to what you offer with Hopcroft-Karp, if you add another level that distinguishes time intervals with some kind of stream expander.

Thus, you will have a source connected to people, people connected to time intervals, time intervals associated with time breakdowns, and failures connected to the sink.

To describe the breakdown, let's say you have time intervals that start at 10:00, 10:15, 10:30 and 10:45. Temporary disruptions will be 15 minutes. If all meetings last an hour, then the time interval 10:00 will be connected to the breakdown 10: 00-10: 15, as well as 10: 15-10: 30, 10: 30-10: 45 and 10:45 -11: 00.

When connecting time intervals and failures, there must be some modified logic. This is due to the fact that they would have to change the flow rate between the input of time intervals and connections with breakdowns. This is due to the fact that whenever one person receives a binding to a time interval (time interval in a stream = 1), there are several flows in the breakdown (output time 4 = for the example above).

I have not tried one disclaimer. If you say please how well this works.

+1
source share

More articles:


All Articles