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"?