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?

I suppose you want to delete as little EmptyEvents as possible.

In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events.

Proceed as follows:

-
First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order.

• Each time you come across the start-time of an EmptyEvent, if counter > 0, then flag that event for deletion. If counter == 0, put that event (or rather its id) in S.

• Each time you come across the end-time of an EmptyEvent, if counter > 0, then flag that event for deletion. Delete the corresponding event from S (if it is still in there).

• Each time you come across the start-time of a NormalEvent, increase the counter by 1.

• Each time you come across the end-time of a NormalEvent, decrease the counter by 1, flag all EmptyEvents in S for deletion and clear S.

(then delete all the flagged events)

-
Then, choose the largest subset of EmptyEvents, no two intersecting. To do so, sort all EmptyEvents according to end-time. Then just go through these events and greedily select one each time it doesn't intersect with the last selected one.

-
Then, set all the NormalEvent booleans. Set a counter = 0 and prevStart to track the most recent start-time. Sort all NormalEvents start and end-times. Iterate through them in order.

• Each time you come across start-time of NormalEvent e, set e.overlapsStart to counter > 0. Then increase counter by 1. Also set prevStart = e.startTime.

• Each time you come across end-time of a NormalEvent e, decrease the counter by 1 and set e.overlapsEnd to `e.startTime

I'll let you convince yourself of the validity of each step. But here is a good starting point if you are unable to do so :
Interval scheduling on Wikipedia

StackExchange Computer Science Q#112115, answer score: 2