Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Задачка от ЯНДЕКСа  [new]
PavluxaF
Member

Откуда: СПб
Сообщений: 126
Доброго времени суток.

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

автор
DECLARE @T TABLE (ID int Identity(1,1), Start int, Finish int)

INSERT INTO @T (Start, Finish)
SELECT 1, 5
UNION ALL
SELECT 1, 3
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 1, 9
UNION ALL
SELECT 11, 20
UNION ALL
SELECT 15, 19
UNION ALL
SELECT 15, 25
UNION ALL
SELECT 30, 40
UNION ALL
SELECT 29, 41


Проблема в том что я не могу понять условия (что от меня хотят) и в каком виде это представить
Если я понял "правильно??" они хотят увидеть 2 периода 9 - 11 и 25 - 29


Прошу поделиться изящным решением (свое выложу как допишу)
8 ноя 14, 00:56    [16815209]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
Гавриленко Сергей Алексеевич
Member

Откуда:
Сообщений: 37254
PavluxaF
Проблема в том что я не могу понять условия (что от меня хотят) и в каком виде это представить
Если я понял "правильно??" они хотят увидеть 2 периода 9 - 11 и 25 - 29
Так надо было спросить у предлагавшего вам проверить ваши скилы.
8 ноя 14, 01:06    [16815243]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
Станислав Клевцов
Member

Откуда: Krasnodar-Russia
Сообщений: 566
PavluxaF
Доброго времени суток.

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

автор
DECLARE @T TABLE (ID int Identity(1,1), Start int, Finish int)

INSERT INTO @T (Start, Finish)
SELECT 1, 5
UNION ALL
SELECT 1, 3
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 1, 9
UNION ALL
SELECT 11, 20
UNION ALL
SELECT 15, 19
UNION ALL
SELECT 15, 25
UNION ALL
SELECT 30, 40
UNION ALL
SELECT 29, 41


Проблема в том что я не могу понять условия (что от меня хотят) и в каком виде это представить
Если я понял "правильно??" они хотят увидеть 2 периода 9 - 11 и 25 - 29


Прошу поделиться изящным решением (свое выложу как допишу)


Известная задачка

Результат должен быть :

автор
1 9
11 25
29 41
8 ноя 14, 01:08    [16815250]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
PavluxaF
Member

Откуда: СПб
Сообщений: 126
Скилы предлагают проверить онлайн (спросить не у кого)

Станислав Клевцов
в моем понимании Ваш ответ это обратная задача, но это не меняет сути
как решать? В голову лезут курсоры, но execution plan будет ЖЕСТЬ))
8 ноя 14, 01:15    [16815277]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
Mind
Member

Откуда: Лучший город на Земле
Сообщений: 2322
PavluxaF,

Вроде оно
Calculating Gaps Between Overlapping Time Intervals in SQL
8 ноя 14, 01:28    [16815301]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
aleks2
Guest
Mind
PavluxaF,

Вроде оно
Calculating Gaps Between Overlapping Time Intervals in SQL

Что-то он там намутил сильно заковыристо.

Задача то тривиальна.

DECLARE @T TABLE (ID int Identity(1,1), Start int, Finish int)

INSERT INTO @T (Start, Finish)
SELECT 1, 5
UNION ALL
SELECT 1, 3
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 1, 9
UNION ALL
SELECT 11, 20
UNION ALL
SELECT 15, 19
UNION ALL
SELECT 15, 25
UNION ALL
SELECT 30, 40
UNION ALL
SELECT 29, 41
select * from @t

;with
   s as ( select start, row_number() over(order by start) n from @t t where not exists( select * from @t tt where (tt.start<t.start or (tt.start=t.start and tt.id<t.id) ) and tt.finish > t.start) )
,  f as ( select finish, row_number() over(order by finish) n from @t t where not exists( select * from @t tt where (tt.finish>t.finish or (tt.finish=t.finish and tt.id>t.id) ) and tt.start < t.finish) )
select start, finish from s inner join f on s.n = f.n
8 ноя 14, 07:00    [16815570]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
PavluxaF
Member

Откуда: СПб
Сообщений: 126
aleks2 Огромное спасибо.
Решение хорошее и правильное!

Мой конечный вариант
BEGIN
	WITH S AS 
	(
		SELECT [start],ROW_NUMBER()
		OVER 
		(	
			ORDER BY [start]
		) AS [RN] 
		FROM @t T1
		WHERE NOT EXISTS(
							SELECT TOP 1 1 
							FROM @t T2
							WHERE (T2.[start] < T1.[start] AND T2.[finish] > T1.[start])

							UNION ALL 

							SELECT TOP 1 1 
							FROM @t T2
							WHERE (T2.[start]=T1.[start] AND T2.[id] < T1.[id] AND T2.[finish] > T1.[start])
						) 
	),
	F AS 
	(
		SELECT [finish],ROW_NUMBER() 
		OVER 
		(	
			ORDER BY [finish]
		) AS [RN]
		FROM @t T1
		WHERE NOT EXISTS(
							SELECT TOP 1 1
							FROM @t T2 
							WHERE (T2.[finish] > T1.[finish] AND T2.[start] < T1.[finish])

							UNION ALL

							SELECT TOP 1 1
							FROM @t T2 
							WHERE (T2.[finish] = T1.[finish] AND T2.[id] > T1.[id] AND T2.[start] < T1.[finish])
						)
	)
	SELECT [start],[finish]
	FROM S 
	INNER JOIN F on S.[RN] = F.[RN]
END


по сути дела тоже самое
До OVER дошел сам, но с условиями not exists -заблудился (так что взял Ваши).
Еще раз спасибо
8 ноя 14, 12:56    [16815925]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
Andrey Sribnyak
Member

Откуда: Киев
Сообщений: 600
PavluxaF


Прошу поделиться изящным решением (свое выложу как допишу)



Не знаю, насколько "изящное"

ради прикола решил так:

DECLARE @T TABLE (ID int Identity(1,1), Start int, Finish int)

INSERT INTO @T (Start, Finish)
SELECT 1, 5
UNION ALL
SELECT 1, 3
UNION ALL
SELECT 1, 2
UNION ALL
SELECT 1, 9
UNION ALL
SELECT 11, 20
UNION ALL
SELECT 15, 19
UNION ALL
SELECT 15, 25
UNION ALL
SELECT 30, 40
UNION ALL
SELECT 29, 41

SELECT min(num) StartMin, max(num) FinishMax 
FROM (
	SELECT num
		,num - rank() OVER (
			ORDER BY num
			) n
	FROM (
		SELECT DISTINCT num
		FROM 

		(    SELECT 5*5*(a-1)+5*(b-1) + c AS num
			FROM (SELECT 1 a UNION ALL SELECT 2 UNION ALL SELECT 3
			UNION ALL SELECT 4 UNION ALL SELECT 5
			) x CROSS JOIN
			(SELECT 1 b UNION ALL SELECT 2 UNION ALL SELECT 3
			UNION ALL SELECT 4 UNION ALL SELECT 5
			) y CROSS JOIN
			(SELECT 1 c UNION ALL SELECT 2 UNION ALL SELECT 3
			UNION ALL SELECT 4 UNION ALL SELECT 5
			) z
			WHERE 5*5*(a-1)+5*(b-1) + c <= 100
		)  as s join @t t on s.num between start and Finish
)t
)tt
group by n



в любом случае на собеседование не пригласили :)

Значит не факт, что и это правильное
10 ноя 14, 19:02    [16824577]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
zasandator
Member [скрыт] [заблокирован]

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

;with nums9 as
(select * from (values(0),(1),(2),(3),(4),(5),(6),(7),(8),(9))t(num))
, nums (num) as
(
select a.num+b.num*10+c.num*100+d.num*1000
from
	nums9 a,
	nums9 b,
	nums9 c,
	nums9 d
)
, list as
(
select distinct num
from nums n
join @t t
	on n.num between t.Start and t.Finish
)
select t1.num Start, min(t2.num) Finish
from list t1
join list t2
	on t1.num < t2.num
group by t1.num
having t1.num+1 <> min(t2.num)


Решение тяжелое... но правильное. Наверняка можно оптимальнее найти
10 ноя 14, 21:35    [16825097]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
Критик
Member

Откуда: Москва / Калуга
Сообщений: 35872
Блог
select distinct
           (select min(t2.Start)  from @t as t2 where t1.Start between t2.Start and t2.Finish or t1.Finish between t2.Start and t2.Finish) as Start,
	   (select max(t2.Finish) from @t as t2 where t1.Start between t2.Start and t2.Finish or t1.Finish between t2.Start and t2.Finish) as Finish
  from @t as t1
11 ноя 14, 00:45    [16825644]     Ответить | Цитировать Сообщить модератору
 Re: Задачка от ЯНДЕКСа  [new]
DeColo®es
Member

Откуда: Москва
Сообщений: 5503
Блог
Тут, что открытый конкурс на занятие вакантной должности в Яндексе?

О времена, о нравы... :(
11 ноя 14, 05:51    [16825894]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить