Максимальное количество пересечений временных интервалов

Question

Есть таблица, в которой перечислены события с началом и концом действия. У событий есть различные типы. Нужно найти максимальное количество событий, которые происходили одновременно.

Пример таблицы:

event_id	time_start	time_end	event_type
1	2022-10-01 15:01:21	2022-10-01 15:03:21	A
2	2022-10-01 15:02:13	2022-10-01 15:03:10	A
3	2022-10-13 14:18:11	2022-10-13 15:07:01	B
4	2022-10-10 12:04:51	2022-10-10 12:06:28	B
5	2022-10-01 15:03:22	2022-10-01 15:05:43	A

Например, в этой таблице по типу А был момент когда одновременно действовали события id 1 и 2, а у типа B события не пересекались, т.е. результат будет такой:

event_type	max()
A	2
B	1

В какую сторону копать, не понятно :(

BD - Vertica

Answer 1

Создадим таблицу и загрузим в нее данные. Id нас тут не очень будет интересовать.

create table events (
    time_start datetime,
    time_end datetime,
    event_type varchar
);

insert into events values
('2022-10-01 15:01:21', '2022-10-01 15:03:21',  'A'),
('2022-10-01 15:02:13', '2022-10-01 15:03:10',  'A'),
('2022-10-13 14:18:11', '2022-10-13 15:07:01',  'B'),
('2022-10-10 12:04:51', '2022-10-10 12:06:28',  'B'),
('2022-10-01 15:03:22', '2022-10-01 15:05:43',  'A');

Подумаем, как эту задачу можно решить на бумажке/календаре/гугл-календаре. Можно для каждого события нарисовать в календаре полосу между началом и концом. События разного типа — разным цветом. Потом еще раз пройтись от начала до конца, записывая, сколько на каждый момент времени полос одного цвета. Достаточно делать это в тех местах, где начинается или оканчивается очередное событие. А потом из записанных сумм для каждого типа события найти максимум.

Осталось воспроизвести это в SQL. Разобьем каждое событие на две отдельных строки: начало и конец. Кроме того, добавим столбец, обозначающий изменение количества событий. Начало будет обозначать +1 к количеству событий, а конец -1. Остортируем по времени, чтобы получился возрастающий временной ряд.

select time_start as ts, event_type, +1 as cnt from events
union all
select time_end   as ts, event_type, -1 as cnt from events

ts  event_type  cnt
2022-10-01 15:01:21.000000  A   1
2022-10-01 15:02:13.000000  A   1
2022-10-01 15:03:22.000000  A   1
2022-10-10 12:04:51.000000  B   1
2022-10-13 14:18:11.000000  B   1
2022-10-01 15:03:21.000000  A   -1
2022-10-01 15:03:10.000000  A   -1
2022-10-01 15:05:43.000000  A   -1
2022-10-10 12:06:28.000000  B   -1
2022-10-13 15:07:01.000000  B   -1

Теперь нужно для каждой строки найти сумму всех значений cnt выше неё с с разбивкой по отдельным event_type. Это делается при помощи running/cumulative sum. В Vertica — analytic sum:

select ts, event_type, cnt, sum(cnt) OVER (PARTITION BY event_type ORDER BY ts) as cnt_cum from (
    select time_start as ts, event_type, +1 as cnt from events
    union all
    select time_end as ts, event_type, -1 as cnt from events
) e1

ts  event_type  cnt cnt_cum
2022-10-01 15:01:21.000000  A    1  1
2022-10-01 15:02:13.000000  A    1  2
2022-10-01 15:03:10.000000  A   -1  1
2022-10-01 15:03:21.000000  A   -1  0
2022-10-01 15:03:22.000000  A    1  1
2022-10-01 15:05:43.000000  A   -1  0
2022-10-10 12:04:51.000000  B    1  1
2022-10-10 12:06:28.000000  B   -1  0
2022-10-13 14:18:11.000000  B    1  1
2022-10-13 15:07:01.000000  B   -1  0

Осталось найти максимальные значения среди cnt_cum для каждого event_type:

select event_type, max(cnt_cum) from (
  select ts, event_type, cnt, sum(cnt) OVER (PARTITION BY event_type ORDER BY ts) as cnt_cum from (
    select time_start as ts, event_type, +1 as cnt from events
    union all
    select time_end as ts, event_type, -1 as cnt from events
  ) e1
order by ts
) e2 group by event_type;

event_type  max
B   1
A   2

БЛОГ НА HUSL

Максимальное количество пересечений временных интервалов

Ответы (1 шт):