Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Разбиение пересекающихся интервалов на подинтервалы  [new]
fsmk
Member

Откуда:
Сообщений: 17
Добрый день всем! Скажу сразу, поиском пользовался, варианты не совсем рабочие находил. Суть проблемы:

есть табличка интервалов например на прямой, координаты интервалов:

x1 x2
1 10
1 10
1 10
1 10
4 авг 18, 13:50    [21629908]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
uaggster
Member

Откуда:
Сообщений: 757
fsmk, это Gaps and Islands in Sequences
https://www.red-gate.com/simple-talk/sql/t-sql-programming/the-sql-of-gaps-and-islands-in-sequences/
4 авг 18, 13:54    [21629911]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
fsmk
Member

Откуда:
Сообщений: 17
случайно запостил, не нашел как отредактировать пост пишу дальше:

есть табличка интервалов например на прямой, координаты интервалов:

x1 x2
1 10
2 11
5 5

Нужно разбить на подинтервалы и получить:

1 2
2 5
5 10
10 11
4 авг 18, 13:56    [21629912]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
fsmk
Member

Откуда:
Сообщений: 17
uaggster,

не совсем то. мне по сути острова нужно тоже делить.
4 авг 18, 14:22    [21629922]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
invm
Member

Откуда: Москва
Сообщений: 9115
declare @t table(x1 int, x2 int);

insert into @t
values
 (1, 10), (2, 12), (5, 5);

with a(x) as
(
 select x1 from @t
 union all
 select x2 from @t
), b as
(
 select x, row_number() over (order by x) as rn from a
)
select
 b1.x, b2.x
from
 b b1 join
 b b2 on b2.rn = b1.rn + 1
where
 b2.x > b1.x
order by
 b1.x;
4 авг 18, 14:32    [21629934]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Deff
Member

Откуда: Пермь
Сообщений: 18323
fsmk
случайно запостил, не нашел как отредактировать пост пишу дальше:

есть табличка интервалов например на прямой, координаты интервалов:

x1 x2
1 10
2 11
5 5

Нужно разбить на подинтервалы и получить:

1 2
2 5
5 10
10 11
Эта задача не решается в один поток. SQL тут не помощник.
Используй другие методы для решения алгоритмических задач.
4 авг 18, 14:34    [21629935]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
fsmk
Member

Откуда:
Сообщений: 17
invm, благодарю!!!!!
4 авг 18, 14:49    [21629945]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
fsmk
Member

Откуда:
Сообщений: 17
invm,

insert into @t
values
(1, 2), (3, 5), (3, 7);

с такими значениями выдает лишний интервал 2 - 3, от ведь не пересекается?
6 авг 18, 11:23    [21631020]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
invm
Member

Откуда: Москва
Сообщений: 9115
fsmk,

Разбейте исходный набор на два - интервалы, которые не пересекаются с другими и остальные.
Первый пойдет напрямую в результат, а ко второму примените показанное преобразование.
6 авг 18, 12:33    [21631167]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20181
Если по рабоче-крестьянски, то можно так:

with test (start,stop) as (
select 1,2 union all
select 3,4 union all
select 4,5 union all
select 6,8 union all
select 7,9 union all
select 8,10 union all
select 11,14 union all
select 12,13
),
total(point,weight) as (
select start,1 from test
union all
select stop,-1 from test
),
weights (point, weight, rn) as (
select t1.point, sum(t2.weight), row_number() over (order by t1.point)
from total t1, total t2
where t1.point >= t2.point
group by t1.point)
select t1.point start, t2.point stop
from weights t1, weights t2
where t1.rn=t2.rn-1
and t1.weight > 0;
6 авг 18, 13:19    [21631270]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
demind10
Member

Откуда:
Сообщений: 17
fsmk, можно в решение invm добавить проверку на попадание внутрь существующего интервала.
declare @t table(x1 int, x2 int);

insert into @t
values
 (1, 10), (2, 12), (5, 5),(6,13),(15,20);

with a(x) as
(
 select x1 from @t
 union all
 select x2 from @t
), b as
(
 select x, row_number() over (order by x) as rn from a
)
select *
from (
select
 b1.x, b2.x as y
from
 b b1 join
 b b2 on b2.rn = b1.rn + 1
where
 b2.x > b1.x
--order by
-- b1.x
 ) D
 where exists (select * from @t where x>=x1 and y<=x2)
 order by x;
6 авг 18, 22:22    [21632229]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Щукина Анна
Member

Откуда:
Сообщений: 1466
fsmk,
+ сборная солянка на основе лучших моментов из предыдущих решений + небольшая изюминка собственного приготовления... :)
with
-- Исходные данные:
  intervals(x1, x2) as
    (
      select * 
        from (
               values 
                 (-5, -3),
                 ( 1,  2),
                 ( 2,  5),
                 ( 5, 10),
                 (10, 11),
                 (15, 18)
             ) v(x1,x2)
    )
-- Разворот интервалов в точки (можно использовать UNPIVOT при желании)
, point (p, f) as
    (
      select x1, 1 f from intervals
      union all
      select x2, -1 f from intervals
    )
-- Нумерация точек и расчет "эрланга"
, numeredPoint (p, rn, erlang) as
    (
      select p
           , row_number() over (order by p) as rn
           , sum(f) over(order by p) erlang
       from point
    )
, newIntervals (newX1, newX2) as
-- Свёртка точек в новые интервалы + фильтрация "мусора"
    (
      select p1.p as newX1
           , p2.p as newX2
        from numeredPoint p1
        join numeredPoint p2
          on p2.rn = p1.rn + 1
       where p2.p > p1.p
         and p1.erlang > 0
    )
-- Показ результата:
select * 
  from newIntervals

желающим проверок - ссылка на sqlfiddle.com
7 авг 18, 06:18    [21632348]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20181
Щукина Анна, Вам не кажется, что с учётом
row_number() over (order by p) as rn
и
on p2.rn = p1.rn + 1
условие
where p2.p > p1.p
является избыточным?
7 авг 18, 07:23    [21632365]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Щукина Анна
Member

Откуда:
Сообщений: 1466
Akina,

все данные для тестирования доступны. попробуйте с условием, без условия и почувствуйте разницу ;)
7 авг 18, 07:25    [21632367]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20181
Щукина Анна, да, не посмотрел, что свёртка выполняется именно на этом этапе, а не на предыдущем. Сорри.
7 авг 18, 08:31    [21632389]     Ответить | Цитировать Сообщить модератору
 Re: Разбиение пересекающихся интервалов на подинтервалы  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20181
PS. Старайтесь всё же пользоваться менее тормозными fiddle-ресурсами. Скажем, db<>fiddle или db-fiddle.
7 авг 18, 08:33    [21632391]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить