CODEWITHSUNDEEP
sqlalgorithmsorting
Mr. DOS
Mr. DOS

Reputation: 433

How do I determine the time at which the largest number of simultaneously events occurred?

Given a list of historical events, each of which ran for some number of seconds and has a non-unique start time, how can “best” I determine the range in time at which the maximal number of events was occurring? (In this case, for “best”, the dataset is stored in a SQL database, so I'm probably looking for something that balances a low number of queries with returning a small dataset to the client; there are potentially hundreds of events in the time interval under scrutiny.)

For example, given these events:

The most events are occurring from times 9-10 with 3 events occurring simultaneously.

One approach that comes to mind is iterating over the entire interval of time over which the events occur and, at each point, evaluating how many events were occurring there, then storing the maximum; but there surely must be some more efficient approach.

Upvotes: 1

Views: 122

Answers (2)

D Stanley
D Stanley

Reputation: 152624

Since the "max" would occur when one of the events starts, you could do a self-join looking for the number of events in progress at that time:

SELECT TOP 1 MAX(e1.StartDate), COUNT(e2.eventID) FROM event e1
INNER JOIN event e2 
  on e1.StartDate BETWEEN e2.StartDate 
                      AND DATEADD(second,e2.Duration,e2.StartDate)
GROUP BY e1.EventID
ORDER BY COUNT(e2.eventID) DESC

Upvotes: 1

OopsUser
OopsUser

Reputation: 4774

1.Take all your event begin and event end times and put in some struct like :

struct EventBeginOrEnd
{
bool begin; // True if event begin, false if end
int time;
}

Put all the events in a List<EventBeginOrEnd> myEventList and sort it.

2.Hold few counters :

  • CurrentEventCount - counts how many events happening now.
  • MaxEventsCountSoFar - counts the maximum events in one time measured till now.
  • TheMaxTime - the time in which the maximum was measured.

3.iterate over myEventList and in each element check if he is begin or end, if begin increase CurrentEventCount otherwise decrease.

4.When CurrentEventCount is larger then MaxEventsCountSoFar update like this : 

MaxEventsCountSoFar=MaxEventsCountSoFar;
TheMaxTime=currentElement.time;

Notice that this allows you to use floating point for time and not only int, because you are not iterating over time but over the events you have.

The complexity is O(n*Log(n)) because of the sort.

Upvotes: 0

Related Questions