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 EmptyEvents 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 NormalEvents 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?