Объединение перекрывающихся временных интервалов на основе иерархии в SQL

Question

Я пытаюсь решить проблему, в которой я хочу объединить перекрывающиеся интервалы для данного идентификатора столбца, но я также хочу объединить их на основе иерархии / приоритета.У меня есть start_time и stop_time для каждого интервала, и каждый интервал имеет иерархию / приоритет, связанный с ним.

Это следующие столбцы в таблице:

id, start_time, stop_time, priority

Мне удалось решить проблему, когда у меня нет приоритета, но я борюсь с этим.

Red colour: p1 (priority 1)
Blue Colour: p2 (priority 2)
Green colour: p3 (priority 3)

Обратите внимание, что в приведенном ниже примере ввода у нас будет 9 строк с одинаковым идентификатором, а на выходе будет 6 строк.Обратите внимание, что для некоторых идентификаторов могут быть только некоторые значения приоритета или только одно, решение должно позаботиться об этом.

ожидаемый ввод и вывод:

Answer 1

Ниже для BigQuery Standard SQL

#standardSQL
WITH check_times AS (
  SELECT id, start_time AS time FROM `project.dataset.table` UNION DISTINCT
  SELECT id, stop_time AS time FROM `project.dataset.table` 
), distinct_intervals AS (
  SELECT id, time AS start_time, LEAD(time) OVER(PARTITION BY id ORDER BY time) stop_time
  FROM check_times
), deduped_intervals AS (
  SELECT a.id, a.start_time, a.stop_time, MIN(priority) priority
  FROM distinct_intervals a
  JOIN `project.dataset.table` b
  ON a.id = b.id 
  AND a.start_time BETWEEN b.start_time AND b.stop_time 
  AND a.stop_time BETWEEN b.start_time AND b.stop_time
  GROUP BY a.id, a.start_time, a.stop_time
), combined_intervals AS (
  SELECT id, MIN(start_time) start_time, MAX(stop_time) stop_time, ANY_VALUE(priority) priority 
  FROM (
    SELECT id, start_time, stop_time, priority, COUNTIF(flag) OVER(PARTITION BY id ORDER BY start_time) grp
    FROM (
      SELECT id, start_time, stop_time, priority, 
        start_time != IFNULL(LAG(stop_time) OVER(PARTITION BY id ORDER BY start_time), start_time) OR
        priority != IFNULL(LAG(priority) OVER(PARTITION BY id ORDER BY start_time), -1) flag
      FROM deduped_intervals
    )
  )
  GROUP BY id, grp
)
SELECT *
FROM combined_intervals
-- ORDER BY id, start_time

Если применить к образцу данных из вашего вопроса - результат

Можете ли вы также поделиться решением, в котором мы объединяем интервалы на основе только идентификатора и столбца без приоритета

Я просто слегка скорректировал приведенный выше запрос, чтобы игнорировать приоритет

#standardSQL
WITH check_times AS (
  SELECT id, start_time AS TIME FROM `project.dataset.table` UNION DISTINCT
  SELECT id, stop_time AS TIME FROM `project.dataset.table` 
), distinct_intervals AS (
  SELECT id, TIME AS start_time, LEAD(TIME) OVER(PARTITION BY id ORDER BY TIME) stop_time
  FROM check_times
), deduped_intervals AS (
  SELECT a.id, a.start_time, a.stop_time 
  FROM distinct_intervals a
  JOIN `project.dataset.table` b
  ON a.id = b.id 
  AND a.start_time BETWEEN b.start_time AND b.stop_time 
  AND a.stop_time BETWEEN b.start_time AND b.stop_time
  GROUP BY a.id, a.start_time, a.stop_time
), combined_intervals AS (
  SELECT id, MIN(start_time) start_time, MAX(stop_time) stop_time 
  FROM (
    SELECT id, start_time, stop_time, COUNTIF(flag) OVER(PARTITION BY id ORDER BY start_time) grp
    FROM (
      SELECT id, start_time, stop_time, 
        start_time != IFNULL(LAG(stop_time) OVER(PARTITION BY id ORDER BY start_time), start_time) flag
      FROM deduped_intervals
    )
  )
  GROUP BY id, grp
)
SELECT *
FROM combined_intervals
-- ORDER BY id, start_time   

с результатом

Row id  start_time  stop_time    
1   1   0           36   
2   1   41          47   

Answer 2

Это проблема "объединения" островов. Одно из решений состоит в том, чтобы найти, где начинаются острова, и сделать кумулятивную сумму начальных чисел. Вы можете определить начало, увидев, где нет совпадений:

select id, priority, min(start_time), max(stop_time)
from (select t.*,
             countif(coalesce(prev_stop_time, stop_time) < stop_time) over (partition by id, priority order by start_time) as grp
      from (select t.*,
                   max(stop_time) over (partition by id, priority order by start_time rows between unbounded preceding and 1 preceding) as prev_stop_time
            from t
           ) t
      ) t
group by id, priority, grp;