SQL algorithm for most overlapping events

Question

The Problem

I'm looking for a query to help me solve the following:

• I have a series of events
• Each event has a start and end date.
• Many of these events overlap
• The answer I'm looking for is the maximum number of events that overlap

Example

Say I have 5 events:

• 1 Jan -> 9 Jan
• 7 Jan -> 12 Jan
• 8 Jan -> 10 Jan
• 10 Jan -> 15 Jan
• 12 Jan -> 17 Jan

3 of these events overlap 9th January, which is the maximum overlapping events, so the answer is 3.

(There are also 3 events overlapping on 10th January, but that's the same answer)

What I've Tried

If I was doing this in memory, I could do this:

• For each event:
  • Get the start date
  • Count the dates that include this event
• Pick the event with the highest count.

But there are 2 issues with this:

• It doesn't appear to be very efficient
• It isn't very SQL-y (ie. is procedural rather than set-based)

Question

How can I implement something like this in SQL?

Notes

• I don't care to find the start / end dates of the most overlapping events. I just need a count
• I don't care how often the maximum occurs, I just need the maximum. So, in the example above, I know there are two occasions where 3 events overlap, but I just need the "3".
• If event A ends on the same day as event B starts, they are considered to be overlapping

Answer 1

It might be more performant to write this in code, not sql.

In code, I would sort the items by start date, then end date. Walk through them and check if it overlaps with the next item. If it does, increment its overlap counter and repeat: check the next item overlaps with your item. If it doesn't, move on to the next.

In SQL, you can do it with a self join to list all the overlaps.

This will show you all overlaps:

select a.eventid from events a inner join events b on a.end > b.start and a.start < b.end 

You can then group them by eventid, select the count and take the event with the max count.

select top 1 eventid, count(*) as c from (select a.eventid from events a inner join events b on a.end > b.start and a.start < b.end) group by eventid order by c desc 

Answer 2

Another strategy in relational databases is to have a table with a record for each calendar day. This helps in situation where you're trying to determine days that don't exist in your system. It's just easier for them to work with data that are there instead of relying on the database to create data by calculation.

With that table and your table of events, you could join them together and do some simple aggregation (SQL Server):

create table Datelist ( HistoryDate datetime not null ) insert into DateList (HistoryDate) values ( '1/1/2018') , ('1/2/2018') ... create table event ( StartDate datetime not null , EndDate datetime not null ) insert into event (StartDate, EndDate) values ('01/01/2018', '01/09/2018') , ('01/07/2018', '01/12/2018') , ('01/08/2018', '01/10/2018') , ('01/10/2018', '01/15/2018') , ('01/12/2018', '01/17/2018') select max(c.EventCount) as maxEvents from ( select d.HistoryDate , count(d.HistoryDate) as EventCount from DateList as d inner join event as e on d.HistoryDate between e.StartDate and e.EndDate group by d.HistoryDate ) as c 

The query isn't too hard to read, but you have to understand the contents of the pre-populated "DateList" table. You can run the subquery to see the actual list of each date for testing purposes.