Условие

Дана таблица incidents(incident_id, start_ts, end_ts, severity). Нужно посчитать для каждого момента времени количество одновременно активных инцидентов и определить периоды, когда «активность» превышает заданный порог K.

Дополнительно: объединить overlap-периоды одного и того же типа в непрерывные «episodes».

Решение

Подход (sweep line)

Классический алгоритм для интервалов:

Преобразуем каждое начало/конец в событие (+1, −1).
Сортируем по времени.
Кумулятивная сумма даёт «количество активных в момент».
Когда сумма пересекает K вверх → начинается «hot interval»; вниз → заканчивается.

WITH events AS (
  SELECT start_ts AS ts, +1 AS delta FROM incidents
  UNION ALL
  SELECT end_ts   AS ts, -1 AS delta FROM incidents
),
ordered AS (
  SELECT ts,
         SUM(delta) OVER (ORDER BY ts ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS active_n
  FROM events
),
flagged AS (
  SELECT ts, active_n,
         CASE WHEN active_n >= 5 THEN 1 ELSE 0 END AS hot,
         LAG(CASE WHEN active_n >= 5 THEN 1 ELSE 0 END)
              OVER (ORDER BY ts) AS prev_hot
  FROM ordered
),
runs AS (
  SELECT ts, active_n, hot,
         SUM(CASE WHEN hot != COALESCE(prev_hot, 0) THEN 1 ELSE 0 END)
              OVER (ORDER BY ts) AS run_id
  FROM flagged
)
SELECT run_id, MIN(ts) AS hot_start, MAX(ts) AS hot_end,
       MAX(active_n) AS peak
FROM runs
WHERE hot = 1
GROUP BY run_id
ORDER BY hot_start;

Объединение пересекающихся в episodes

Если два инцидента имеют overlap, они объединяются:

WITH ordered AS (
  SELECT incident_id, start_ts, end_ts,
         MAX(end_ts) OVER (
           ORDER BY start_ts
           ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING
         ) AS prev_end
  FROM incidents
),
labeled AS (
  SELECT *,
         CASE WHEN start_ts > COALESCE(prev_end, start_ts - INTERVAL '1 sec')
              THEN 1 ELSE 0 END AS new_grp
  FROM ordered
),
grouped AS (
  SELECT *,
         SUM(new_grp) OVER (ORDER BY start_ts) AS grp
  FROM labeled
)
SELECT grp, MIN(start_ts) AS ep_start, MAX(end_ts) AS ep_end,
       COUNT(*) AS n_incidents
FROM grouped
GROUP BY grp
ORDER BY ep_start;

Альтернатива: считать активные на дискретной сетке

Если шаг 1 минута / 1 час, развернуть generate_series(start, end, INTERVAL '1 min') и считать по сетке. Это проще, но дороже.

SELECT g.t,
       COUNT(*) AS active
FROM generate_series('2024-01-01', '2024-01-31', INTERVAL '1 min') g(t)
JOIN incidents i ON g.t BETWEEN i.start_ts AND i.end_ts
GROUP BY g.t
HAVING COUNT(*) >= 5;

Подводные камни

Совпадающие таймстампы (start = end другого инцидента): формальные одновременные события — порядок обработки +1/−1 влияет. Конвенция: сначала +1 (нач), потом −1 (конец) — иначе занижение.
end_ts NULL (инцидент ещё активен): подставьте NOW() или 'infinity'::timestamp.
Open vs closed интервал: [start, end) или [start, end] — разные результаты на границе.
Sweep line vs дискрет: на 1млн инцидентов sweep быстрее в 100×, дискрет даёт «по таймштампу», что иногда нужно.
Severity в episodes: при объединении нескольких инцидентов разной severity в один episode — нужна агрегация (max severity, count).
Window function без партиции: для multi-tenant (по client_id) не забудьте PARTITION BY client_id во всех window-функциях.

Эталонный ответ

Sweep line: +1/−1 события → cumsum по времени → активные. «Hot intervals» = последовательные точки выше порога, групируем через LAG + cumsum. Объединение пересекающихся через MAX(end) OVER ... PRECEDING и cumsum новых групп.

Rekor — расчёт периодов активных инцидентов с пересечениями (Allen interval algebra)