Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest to highest priority, so I will have a list like:
Starts Ends Event
---------------------------------
0 12 Background
2 3 Event A
4 7 Event B
6 9 Event C
6 10 Event D
and I want to generate from this the following schedule
Starts Ends Event
---------------------------------
0 3 Background
2 3 Event A
3 4 Background
4 6 Event B
6 10 Event D
10 12 Background
Of course there is the naive O(n²) algorithm
schedule: []
for each currentEvent in events:
piecesToAdd = [currentEvent]
for each eventSoFar in schedule:
determine the overlap
modify eventSoFar and piecesToAdd to remove overlap
append piecesToAdd to schedule
but I was wondering if there is a more efficient way.
If all the time slots are integers, I thought I could just fill a big array at the start with
Starts Ends Event
---------------------------------
0 1 Background *
1 2 Background *
2 3 Background *
3 4 Background
...
but in general I do not want to (and probably cannot) assume that this will be the case. Still, if non-integer time slots are the exception rather than the rule, it may be better to start out like this and split the predefined slots only when needed. But then I need a postprocessing step to consolidate all consecutive slots with the same event, i.e. collapse the lines marked * in the example above into a single "Background: starts 0, ends 3" entry.
It looks like this will be scripted in PHP so any language-specific tricks are welcome, but I am mainly curious about the most efficient way to program this in general.