Create a schedule from overlapping events
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.