# #StackBounty: #algorithms #efficiency #intervals #ordering Algorithm for detecting overlaps

### Bounty: 50

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?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.