I want to do something similar to Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). using Hopcroft-Karp Algorithm. But my additional requirement is that my time intervals are overlapping. Eg. The time slots can be 10am-11am or 10.15am to 11.15am. So if I choose 10am to 11 am slot, I don't want to choose 10.15 am to 11.15 am slot. Is it possible to achieve this without hitting the performance badly?
-
I'm looking for this too using Constraint Programming. @hakank seems to be an expert in this! Closest I've got: stackoverflow.com/questions/20631657/…Marcus– Marcus2013-12-19 16:09:24 +00:00Commented Dec 19, 2013 at 16:09
Add a comment
|
1 Answer
You could use a flow algorithm similar to what your proposing with Hopcroft-Karp if you add another level distinguishing time slots with some sort of flow expander.
So you would have a source connected to the people, people connected to time slots, time slots connected to time breakdowns, and breakdowns connected to a sink.
To further describe the breakdowns, say you have time slots that start at 10:00, 10:15, 10:30 and 10:45. The time breakdowns would be at 15 minutes. If all meetings are an hour long then the 10:00 time slot would be connected to the 10:00-10:15 breakdown as well as the 10:15-10:30, 10:30-10:45 and 10:45-11:00 breakdowns.
There would have to be some modified logic at the connection between the time slots and the breakdowns. That is because their would have to be a change in flow values between the input of the time slots and the connections to the breakdowns. This is because whenever one person gets assigned to a time slot (time slot in-flow = 1) there are multiple flows to the breakdown (time slot out-flow = 4 per example above).
One disclaimer I haven't tried this. If you do please tell us if/how well it works.
