Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Поиск min и max границ пересекающихся отрезков  [new]
диапазон
Guest
Есть отрезки. Они могут разнообразно пересекаться, так, что левая и правая границы могут:
1. Быть обе внутри другого отрезка: 0-5 и 0-8
2. Только одна из границ внутри другого отрезка, тогда как вторая граница - во вне: 1-5 и 4-8
3. Находиться рядом: 0-5 и 6-10
4. Находиться на расстоянии: 1-5 и 7-10

Задача: найти левую и правую границы, сложив пересекающиеся и смежные отрезки.

Я разделил построчно отрезки в исходной таблице, которые должны быть объединены в один отрезок

;WITH tb (a,b) AS (
  SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
                         (13,15),(12,17),(13,100), 
                         (150,200),(160,201))a(a,b)
)
SELECT distinct MIN(t1.a),MAX(t2.b) FROM tb t1
  CROSS APPLY tb t2
WHERE t1.a - t2.a <= 1 AND (t1.a BETWEEN t2.a AND t2.b OR t2.a BETWEEN t1.a AND t1.b)  and t2.a - t1.b <= 1 and t2.b - t1.b >=1
GROUP by CASE WHEN t1.a < t2.a THEN t1.a else 0 END, CASE WHEN t1.b < t2.b THEN t2.b else 0 END

То есть на выходе должно получиться
ab
010
12100
150201


Но приведенный селект это не решение. Это просто перебор решения.
Как я понимаю, наверное тут нужна рекурсия. Или как?
16 июл 17, 02:14    [20647697]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
диапазон
Guest
В примере нет смежных отрезков. Добавляю

;WITH tb (a,b) AS (
  SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
                         (13,15),(12,17),(18,45),(13,100),   -- тут смежный. Считается по правой меньшей и левой большей границам 
                         (150,200),(160,201))a(a,b))
16 июл 17, 02:16    [20647698]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
court
Member

Откуда:
Сообщений: 1956
диапазон,

Запрос на укрупнение периодов
16 июл 17, 10:11    [20647800]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
aleks2
Guest
диапазон
Как я понимаю, наверное тут нужна рекурсия. Или как?


Рекурсии не надо

Идея очень простая
1. Начал стока же скока концов. Независимо от числа перекрытий. Начала и концы можно пронумеровать по-порядку
2. Концом для некоего начала N является конец с тем же номером N.
3. Началом является начало любого отрезка, которое ничем не перекрыто.
4. Концом является конец любого отрезка, который ничем не перекрыт.
16 июл 17, 16:36    [20648248]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
диапазон
Guest
court,

Спасибо. Нашел один вариант. Пытаюсь осмыслить.
17 июл 17, 01:22    [20648865]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
диапазон
Guest
Нет, похоже там по ссылке нет особо решений.
24 июл 17, 02:12    [20668477]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
Добрый Э - Эх
Guest
диапазон
Нет, похоже там по ссылке нет особо решений.
так бы и сказал - что ты не понял решений или не смог адаптировать их под нюансы своей задачи.
24 июл 17, 04:22    [20668496]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
Добрый Э - Эх
Guest
диапазон
Нет, похоже там по ссылке нет особо решений.

Прошел по ссылке, нашел в ней своё же сообщение, подставил в написанный в нем запрос твои тестовые данные, подправил условие проверки "смежных" диапазонов и получил требуемый тебе результат...

-- твои тестовые данные:
;WITH tb (a,b) AS (
  SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
                         (13,15),(12,17),(18,45),(13,100),   -- тут смежный. Считается по правой меньшей и левой большей границам 
                         (150,200),(160,201))a(a,b))
--
-- мой запрос "из ссылки":
select min(a) as x_a, max(b) as x_b
  from (
         select  a, b, sum(sog) over(order by a,b) as grp_id
           from (
                  select a, b,
                         case 
                           when max(b) 
                               over(order by a, b 
                                        rows between unbounded preceding
                                                         and 1 preceding
                                   ) >= a - 1 -- тут добавлено "минус один" для учета "смежности"
                           then 0 
                           else 1 
                         end as sog 
                    from tb
                ) v0
       ) v1
 group by grp_id;


-- результат запроса:
x_a   x_b
---   ---
  0    10
 12   100
150   201
on-line проверка на sqlfiddle.com
24 июл 17, 05:15    [20668505]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
aleks2
Guest
Добрый Э - Эх

-- твои тестовые данные:
;WITH tb (a,b) AS (
  SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
                         (13,15),(12,17),(18,45),(13,100),   -- тут смежный. Считается по правой меньшей и левой большей границам 
                         (150,200),(160,201))a(a,b))
--
-- мой запрос "из ссылки":
select min(a) as x_a, max(b) as x_b
  from (
         select  a, b, sum(sog) over(order by a,b) as grp_id
           from (
                  select a, b,
                         case 
                           when max(b) 
                               over(order by a, b 
                                        rows between unbounded preceding
                                                         and 1 preceding
                                   ) >= a - 1 -- тут добавлено "минус один" для учета "смежности"
                           then 0 
                           else 1 
                         end as sog 
                    from tb
                ) v0
       ) v1
 group by grp_id;


-- результат запроса:
x_a   x_b
---   ---
  0    10
 12   100
150   201
on-line проверка на sqlfiddle.com



Бред.

Гораздо проще и очевидней.
[SRC;WITH tb (a,b) AS (
SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
(13,15),(12,17),(18,45),(13,100), -- тут смежный. Считается по правой меньшей и левой большей границам
(150,200),(160,201))a(a,b))
--
-- начала
, a0 as ( select distinct a from tb as t where not exists( select * from tb as x where t.a between x.a and x.b and x.a < t.a ))
, a as ( select a, n = row_number() over(order by a) from a0 )
-- концы
, b0 as ( select distinct b from tb as t where not exists( select * from tb as x where t.b between x.a and x.b and t.b < x.b ))
, b as ( select b, n = row_number() over(order by b) from b0 )
select a.a, b.b from a inner join b on a.n = b.n[/SRC]
24 июл 17, 06:02    [20668511]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
aleks2
Guest
;WITH tb (a,b) AS (
  SELECT a,b from (VALUES(1,3),(2,5),(2,6),(7,10),(8,10),(0,7),
                         (13,15),(12,17),(18,45),(13,100),   -- тут смежный. Считается по правой меньшей и левой большей границам 
                         (150,200),(160,201))a(a,b))
--
-- начала
, a0 as ( select distinct a from tb as t where not exists( select * from tb as x where t.a between x.a and x.b and x.a < t.a )) 
, a as ( select a, n = row_number() over(order by a) from a0 )
-- концы
, b0 as ( select distinct b from tb as t where not exists( select * from tb as x where t.b between x.a and x.b and t.b < x.b ))
, b as ( select b, n = row_number() over(order by b) from b0 )
select a.a, b.b from a inner join b on a.n = b.n
24 июл 17, 06:03    [20668513]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
Добрый Э - Эх
Guest
aleks2
Бред.

Гораздо проще и очевидней.
Ты уж определись, "проще и очевидней" или "не позорься".
Ссылку-то до конца дочитай. Там специально для тебя есть приведенное тобой нафталиновое решение Ицика Бен-Гана в моей редакции. То, что ты смог в него прикрутить row_number, конечно же, прям достижение.... Интересно, сам придумал, или подглядел у меня же, но пятью годами ранее?

З.Ы.
Смотрю, словарь синонимом русского языка ты себе так и не купил. Что-то более внятное, чем слово "бред" писать так и не научился...
24 июл 17, 06:39    [20668523]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
aleks2
Guest
Добрый Э - Эх
aleks2
Бред.

Гораздо проще и очевидней.
Ты уж определись, "проще и очевидней" или "не позорься".
Ссылку-то до конца дочитай. Там специально для тебя есть приведенное тобой нафталиновое решение Ицика Бен-Гана в моей редакции. То, что ты смог в него прикрутить row_number, конечно же, прям достижение.... Интересно, сам придумал, или подглядел у меня же, но пятью годами ранее?

З.Ы.
Смотрю, словарь синонимом русского языка ты себе так и не купил. Что-то более внятное, чем слово "бред" писать так и не научился...

Зачем читать бред?

Группировки и прочая ненужная хрень - остаются ненужной хренью.
Можно, канешно, штаны и через голову одевать.
Только нужно ли?
24 июл 17, 06:43    [20668525]     Ответить | Цитировать Сообщить модератору
 Re: Поиск min и max границ пересекающихся отрезков  [new]
Добрый Э - Эх
Guest
aleks2
Зачем читать ...
да оно и видно, что читать - это прям не твое...
24 июл 17, 06:48    [20668527]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить