Author |
Topic: Finding all overlapping events (Read 2012 times) |
|
blackJack
Junior Member
2b \/ ~2b
Gender: 
Posts: 55
|
 |
Finding all overlapping events
« on: Apr 25th, 2011, 4:50am » |
 Quote  Modify
|
There are number of events each having ... startTime, endTime and flag as hasConflict.
Events have conflict if they overlap. Initially all events have hasConflict as false, you hvae to write a method to turn this flag as true for events which overlap.
Also, what will be the complexity if given events are already sorted from say, start Time or EndTime.
|
|
 IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Finding all overlapping events
« Reply #1 on: Apr 25th, 2011, 5:47am » |
Quote Modify
|
Let S be events sorted by start time.
foreach event e in S
{
find all the events in S which has start time less than the end time of event e.As s is sorted this can be done in log(size of S) time. Set all these events hasConflict to true.
}
Though finding how many events have conflicts is nlogn,but we might be setting hasConflict repeatedly which would make it O(n2).
So looking for a better approach 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Finding all overlapping events
« Reply #2 on: Apr 25th, 2011, 6:01am » |
Quote Modify
|
Make an array of the start times sorted, and an array of end times sorted (both O(n log n) if they're not already sorted). Run through the two arrays chronologically and set flags at every start time where there are more events that have started than ended ( O(n) ).
Then for each event search if there is a flag set at a time when it's active. (O(log n) per event, O(n log n) total)
Total runtime O(n log n)
Or, run through the events sorted by start time, and as you encounter them drop them in a heap ordered by end time. When there's more than one element in the heap, mark them all as in conflict and then remove all except he one with the last end-time. Look at the next event, remove all events from the heap that have an end-time before the start time of the new event, then insert the new event. Rinse and repeat.
Also O(n log n).
Actually, if the events are already sorted by start time, you can just keep track of the previous event with last end time and get an O(n) algorithm. Using a heap is unnecessary unless you want to know which events overlap (and in that case it'd be O(n2) in the worst-case anyway).
|
| « Last Edit: Apr 25th, 2011, 6:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Finding all overlapping events
« Reply #3 on: Apr 25th, 2011, 6:54am » |
Quote Modify
|
One more n log(n) solution is possible constructing a balanced Interval tree from the events. (Interval tree will be a balanced BST with key as end time and also containing a parameter of maximumEndTime of subtree for each node).
After construction of tree, each node can be traversed in the Interval Tree and any node (other than itself) overlapping with node can be found and both of them can be turned as true.
Quote:| Actually, if the events are already sorted by start time, you can just keep track of the previous event with last end time and get an O(n) algorithm. |
|
Yes, i guess it can be linear if sorted with start Time. I couldnt find any contradictory example for this case.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Finding all overlapping events
« Reply #4 on: Apr 25th, 2011, 9:52pm » |
Quote Modify
|
Quote:
Yes, i guess it can be linear if sorted with start Time. I couldnt find any contradictory example for this case. |
|
Actually on thinking on this, I came up with a scneario.
If the events are (in sorted order of start time) :
(1 - 10) , ( 2 - 4 ) , ( 5 - 8 )
In this case, hasConflict should be true for all three of them, but on comparing just the pairs, we will not get hasConflict for the last event.
|
| « Last Edit: Apr 25th, 2011, 9:52pm by blackJack » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Finding all overlapping events
« Reply #5 on: Apr 26th, 2011, 3:24am » |
Quote Modify
|
If I'm not mistaken, this should work for a set ordered by startTime. It is pretty much what towr suggested.
int k=0;
for( int i=1 ; i<n ; i++ ){
if( startTime[i]<endTime[k] )
hasConflict[i] = hasConflict[k] = true;
if( endTime[i]>=endTime[k] )
k = i;
}
(you can also write event[i].startTime for startTime[i])
|
| « Last Edit: Apr 26th, 2011, 3:26am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print