Algorithm for detecting overlaps
-
05-11-2019 - |
Question
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?
No correct solution