Algorithms/Data structures for collapsing overlapping events on a timeline

Question

I'm looking for an algorithm to do the following. I have a timeline of events which span periods of time which can overlap. I'd like to collapse these events into a single timeline non-overlapping periods of time, each defined by the presence of one or more events.

While conceptually simple, it can be a little messy to catch all the possible cases and split up the timeline appropriately.

To illustrate (here the horizontal axis is time):

Event A   -----
Event B      ----

becomes

Event A   ---
Event A+B    --
Event B        --   

Another Example:

A    -----------
B       ---
C            --

Becomes:

A    ---
A+B     ---
A          --
A+C          --
A              -

Are there any standard algorithms/data structures for doing this?

Answer 1

Put the start and end times of every event in an array, and sort them in non-decreasing order of time (if a "start" and an "end" happen and the same time, break ties by placing the "end" first).

We'll do a sweep line algorithm.

Traverse the sorted array, while maintaining a set of "active" events: whenever you see a start/end time, respectively add or drop the corresponding event from the set, and add (if the active set is non-empty) an event to your solution.

The resulting set of events is disjoint, and can be labelled as needed.