I'm trying to figure out an algorithm for resolving appointment times.
I currently have a naive algorithm that pushes down conflicting
appointments repeatedly, until there are no more
appointments.
# The appointment list is always sorted on start time
appointment_list = [
<Appointment: 10:00 -> 12:00>,
<Appointment: 11:00 -> 12:30>,
<Appointment: 13:00 -> 14:00>,
<Appointment: 13:30 -> 14:30>,
]
Constraints are that appointments:
cannot be after 15:00
cannot be before 9:00
This is the naive algorithm
for i, app in enumerate(appointment_list):
for possible_conflict in appointment_list[i+1:]:
if possible_conflict.start < app.end:
difference = app.end - possible_conflict.start
possible_conflict.end += difference
possible_conflict.start += difference
else:
break
This results in the following resolution, which obviously breaks those constraints, and the last appointment will have to be pushed to the following day.
appointment_list = [
<Appointment: 10:00 -> 12:00>,
<Appointment: 12:00 -> 13:30>,
<Appointment: 13:30 -> 14:30>,
<Appointment: 14:30 -> 15:30>,
]
Obviously this is sub-optimal, It performs 3 appointment moves when the confict could have been resolved with one: if we were able to push the first appointment backwards, we could avoid moving all the subsequent
appointments down.
I'm thinking that there should be a sort of edit-distance approach that would calculate the least number of
appointments that should be moved in order to resolve the scheduling conflict, but I can't get the a handle on the methodology. Should it be breadth-first or depth first solution search. When do I know if the solution is "good enough"?
