2

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
  • just join the table to itself? select id, count(overlap.id) from events left join events overlap on events.dates (overlaplogic) overlap.dates – Ewan Mar 6 '18 at 11:54
  • 1
    Sort your items by time and iterate over them. Each time you pass the beginning or end of an event, keep track of how many are currently occurring. The maximum of that value is your answer. This may be possible to write in idiomatic SQL, but if it isn't, it would be inappropriate to insist on doing it in the query language rather than a programming language. – Kilian Foth Mar 6 '18 at 12:56
2

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
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.