Algorithm for detecting overlaps

This is a real-world application, not a student assignment.

Suppose a list of events of that have `startTime` and `endTime`, and some overlap information. In pseudocode:

``class Event {     Time startTime;     Time endTime;     bool overlapsStart;     bool overlapsEnd; } ``

Events are considered overlaping if and only if their times intersect, but it’s not considered overlap if some event just “touches” another (starts exactly when some other finishes).

There are two types of event: `NormalEvent` and `EmptyEvent`.

What I want?

For each event in the list, I want to:

1) Remove all `EmptyEvent`s that overlap another event of any type. In special, if some `EmptyEvent` overlaps another `EmptyEvent`, only one needs to be removed, so that the overlap ceases.

2) The `NormalEvent`s are first ordered by `startTime`, and then their booleans are set:

• `overlapsStart` is true if the event overlaps some event that comes before it.

• `overlapsEnd` is true if the event overlaps some event that comes after it.

A trivial example:

``event1 = 6:00AM ➜ 8:00AM  ``

and

``event2 = 7:00AM ➜ 9:00AM ``

then:

``event1.overlapsStart == false event1.overlapsEnd == true  event2.overlapsStart == true event2.overlapsEnd == false ``

Another example:

Now, this is what happens if some event “contains” another:

``event1 = 6:00AM ➜ 9:00AM  ``

and

``event2 = 7:00AM ➜ 8:00AM ``

then, first event1 is put before event2, since it starts before. Then:

``event1.overlapsStart == false event1.overlapsEnd == true  event2.overlapsStart == true event2.overlapsEnd == false ``

Naive implementation: I could analyze each event in turn, one by one, looking at all other events. That’s easy, however this is too slow for a large number of events.

My question: What’s an efficient way of solving this?