Search code examples
postgresqlpostgresql-11

Maximum count of overlapping intervals in PostgreSQL

Suppose there is a table structured as follows:

id    start      end
--------------------
01    00:18    00:23
02    00:22    00:31
03    00:23    00:48
04    00:23    00:39
05    00:24    00:25
06    00:24    00:31
07    00:24    00:38
08    00:25    00:37
09    00:26    00:42
10    00:31    00:34
11    00:33    00:38

The objective is to compute the overall maximum number of rows having been active (i.e. between start and end) at any given moment in time. This would be relatively straightforward using a procedural algorithm, but I'm not sure how to do this in SQL.

According to the above example, this maximum value would be 8 and would correspond to the 00:31 timestamp where active rows were 2, 3, 4, 6, 7, 8, 9, 10 (as shown in the schema below).

schema

Obtaining the timestamp(s) and the active rows corresponding to the maximum value is not important, all is needed is the actual value itself.

Solution

  • I was thinking of at first, using generate_series() to iterate every minute and get the count of active intervals for each, then take the max of this.

    You can improve your idea and iterate only "start" values from the table because one of "start" points includes in time interval with maximum active rows.

    select id, start,
    (select count(1) from tbl t where tbl.start between t.start and t."end")
from tbl;

    Here results

    id  start   count
-----------------
1   00:18:00    1
2   00:22:00    2
3   00:23:00    4
4   00:23:00    4
5   00:24:00    6
6   00:24:00    6
7   00:24:00    6
8   00:25:00    7
9   00:26:00    7
10  00:31:00    8
11  00:33:00    7

    So, this query gives you maximum number of rows having been active

    select
    max((select count(1) from tbl t where tbl.start between t.start and t."end"))
from tbl;

    max
-----
8