Create a schedule from overlapping events

Question

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.

Answer 1

One idea would be to construct an additional list of so-called 'changes'. So for your data it would look like this:

Time   Change
0      Background Start
12     Background End
2      Event A Start
3      Event A End
4      Event B Start
...

Then sort by 'Time' O(n log n)

Time   Change
0      Background Start
2      Event A Start
3      Event A End
4      Event B Start
6      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.