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 Dand I want to generate from this the following scheduleStarts  Ends   Event---------------------------------   0     3     Background   2     3     Event A   3     4     Background   4     6     Event B   6     10    Event D   10    12    BackgroundOf 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 schedulebut 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 withStarts  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.
Create a schedule from overlapping events
algorithms;runtime analysis
One idea would be to construct an additional list of so-called 'changes'. So for your data it would look like this:Time   Change0      Background Start12     Background End2      Event A Start3      Event A End4      Event B Start...Then sort by 'Time' O(n log n)Time   Change0      Background Start2      Event A Start3      Event A End4      Event B Start6      Event C Start...Construct an empty balanced binary search tree T. Loop over the changes in order, when a change is an 'event start' add that event to T, when the change is an 'event end' remove it from T. At each change determine the highest priority event and do that until the next change (If it is not different than your last event, in which case just keep doing it).Each of the tree operations is log n, and are done n times so this is all O(n log n). Most languages have some sort of balanced tree that could be used. You could encode the event changes as integers which represent the priority, positive meaning add this event, negative meaning remove this event. This works with non-integer times.