Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

Question

I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, shrinking, or expanding certain parts.

I'm trying to write a program which will do this for me, given a start time, an end time, and a list of calendar events which should either be treated as breaks or sprints. It should return a schedule consisting of as close an approximation to the 52:17 schedule that it reasonably can.

Problem statement:

Input:

• Start of day time
• End of day time
• List of calendar events. User may classify events as "break" (e.g. lunch) or "sprint" (e.g. meetings). These are fixed/immovable.

Output:

• A schedule that approximates the 52:17 intervals, accommodating the aforementioned events.

For example, say I want to work from 8-12 (duration = 240 minutes) uninterrupted. I want to start and end with "sprint". I can find the ideal breakdown as follows:

# Every span starts and ends with a sprint right now, 
# though this can be modified later to handle other circumstances
function n_cycles(duration=240, break_time=17, sprint_time=52):
    cycle_time = break_time + sprint_time
    # If we're looking at an interval of less than the break time
    if duration <= break_time:
        # just call it a break
        return -1
    else if duration <= 52 minutes
        # just call it a sprint
        return 0
    else:
        cycles = 1
        accounted_time = sprint_time
        # If adding another cycle would exceed the duration by more than half
        while accounted_time < duration + cycle_time * 1.5:
            accounted_time = accounted_time + cycle_time
            cycles = cycles + 1
        return cycles

function span_interval(start_time, end_time, break_time=17, sprint_time=52):
    cycles = n_cycles(end_time - start_time, break_time, sprint_time)
    if cycles == -1:
        create_event(start_time, end_time, type=break)
    else if cycles == 0:
        create_event(start_time, end_time, type=sprint)
    else:
        duration = end_time - start_time
        ideal_cycle_time = sprint_time + break_time
        proportion = duration / (ideal_cycle_time + ideal_cycle_time * cycles)
        adjusted_sprint_time = sprint_time * proportion
        adjusted_break_time = break_time * proportion
        create_event(start_time, start_time + adjusted_sprint_time, type=sprint)
        start_time = start_time + adjusted_sprint_time
        for i in 0 to cycles:
            create_event(start_time, start_time + adjusted_break_time, type=break)
            start_time = start_time + adjusted_break_time
            create_event(start_time, start_time + adjusted_sprint_time, type=sprint)
            start_time = start_time + adjusted_sprint_time

So if we do this, we get:

• 8:00-8:48 Sprint #1
• 8:48-9:03 Break
• 9:03-9:52 Sprint #2
• 9:52-10:07 Break
• 10:07-10:56 Sprint #3
• 10:56-11:11 Break
• 11:11-11:59 Sprint #4

Easy! Optimal!

But say I want to add a work event from 10:00-10:15. Currently, I have a "naive" solution where any sprint event is treated as a whole sprint. Then, recursively, the part of the day before and the part of the day after are scheduled. Aside from the fact that the above pseudocode must be modified to end the first half with a break and start the second half with a break (easy), this is also obviously not optimal, since we now have a 15 minute sprint with breaks on either side. I could shift sprint #2 back 7 minutes and compensate on either side, but if I have an event that's 3 hours long, I'm going to need to delete events, not just shift them.

Any ideas about how I can better approach this problem? I'm interested in search algorithms like GAs, but I can't figure out how to structure the problem such that it can be modular and solutions can be heritable.

EDIT: rephrased and formatted in response to comments from D.W.