Создать список, используя шаблоны C ++
т.е.
template struct Node
{
T data;
Node * next;
};
template class List
{
Node *head,*tail;
public:
void push(T const&); // push element
void pop(); // pop element
bool empty() // return true if empty.
};
Затем вы можете написать код, например:
List;
Тип T: не динамический во время выполнения. Это только для времени компиляции.
Для полного примера нажмите «услышать» .
Для учебника по шаблонам C ++ щелкните «услышать» .
Вот решение только для SQL. Я использовал DATETIME для столбцов. На мой взгляд, хранение времени отдельно - ошибка, так как у вас возникнут проблемы, когда время перейдет за полночь. Вы можете отрегулировать это, чтобы справиться с этой ситуацией, если вам нужно. Решение также предполагает, что время начала и окончания НЕ равно NULL. Опять же, вы можете отрегулировать по мере необходимости, если это не так.
Общая суть решения состоит в том, чтобы получить все времена начала, которые не пересекаются с другими промежутками, получить все времена окончания, которые не совпадают. перекрываются с любыми промежутками, а затем сопоставляют два вместе.
Результаты соответствуют ожидаемым результатам, за исключением одного случая, когда проверка вручную выглядит так, как будто у вас есть ошибка в ожидаемом выходе. 6-го числа должен быть промежуток, заканчивающийся в 2009-06-06 10:18: 45.000.
SELECT
ST.start_time,
ET.end_time
FROM
(
SELECT
T1.start_time
FROM
dbo.Test_Time_Spans T1
LEFT OUTER JOIN dbo.Test_Time_Spans T2 ON
T2.start_time < T1.start_time AND
T2.end_time >= T1.start_time
WHERE
T2.start_time IS NULL
) AS ST
INNER JOIN
(
SELECT
T3.end_time
FROM
dbo.Test_Time_Spans T3
LEFT OUTER JOIN dbo.Test_Time_Spans T4 ON
T4.end_time > T3.end_time AND
T4.start_time <= T3.end_time
WHERE
T4.start_time IS NULL
) AS ET ON
ET.end_time > ST.start_time
LEFT OUTER JOIN
(
SELECT
T5.end_time
FROM
dbo.Test_Time_Spans T5
LEFT OUTER JOIN dbo.Test_Time_Spans T6 ON
T6.end_time > T5.end_time AND
T6.start_time <= T5.end_time
WHERE
T6.start_time IS NULL
) AS ET2 ON
ET2.end_time > ST.start_time AND
ET2.end_time < ET.end_time
WHERE
ET2.end_time IS NULL
В MySQL
:
SELECT grouper, MIN(start) AS group_start, MAX(end) AS group_end
FROM (
SELECT start,
end,
@r := @r + (@edate < start) AS grouper,
@edate := GREATEST(end, CAST(@edate AS DATETIME))
FROM (
SELECT @r := 0,
@edate := CAST('0000-01-01' AS DATETIME)
) vars,
(
SELECT rn_date + INTERVAL TIME_TO_SEC(rn_start) SECOND AS start,
rn_date + INTERVAL TIME_TO_SEC(rn_end) SECOND + INTERVAL (rn_start > rn_end) DAY AS end
FROM t_ranges
) q
ORDER BY
start
) q
GROUP BY
grouper
ORDER BY
group_start
То же решение для SQL Server
описано в следующей статье моего блога:
Вот функция для этого:
DROP FUNCTION fn_spans
GO
CREATE FUNCTION fn_spans(@p_from DATETIME, @p_till DATETIME)
RETURNS @t TABLE
(
q_start DATETIME NOT NULL,
q_end DATETIME NOT NULL
)
AS
BEGIN
DECLARE @qs DATETIME
DECLARE @qe DATETIME
DECLARE @ms DATETIME
DECLARE @me DATETIME
DECLARE cr_span CURSOR FAST_FORWARD
FOR
SELECT s_date + s_start AS q_start,
s_date + s_stop + CASE WHEN s_start < s_stop THEN 0 ELSE 1 END AS q_end
FROM t_span
WHERE s_date BETWEEN @p_from - 1 AND @p_till
AND s_date + s_start >= @p_from
AND s_date + s_stop <= @p_till
ORDER BY
q_start
OPEN cr_span
FETCH NEXT
FROM cr_span
INTO @qs, @qe
SET @ms = @qs
SET @me = @qe
WHILE @@FETCH_STATUS = 0
BEGIN
FETCH NEXT
FROM cr_span
INTO @qs, @qe
IF @qs > @me
BEGIN
INSERT
INTO @t
VALUES (@ms, @me)
SET @ms = @qs
END
SET @me = CASE WHEN @qe > @me THEN @qe ELSE @me END
END
IF @ms IS NOT NULL
BEGIN
INSERT
INTO @t
VALUES (@ms, @me)
END
CLOSE cr_span
RETURN
END
Поскольку SQL Server
не имеет простого способа ссылаться на ранее выбранные строки в наборе результатов, это один из редких случаев, когда курсоры в SQL Сервер
работает быстрее, чем решения, основанные на наборах.
Протестировано на 1,440,000
строк, работает в течение 24
секунд для полного набора и почти мгновенно для диапазона дня или 2.
Обратите внимание на дополнительное условие в запросе SELECT
:
s_date BETWEEN @p_from - 1 AND @p_till
Это кажется избыточным, но на самом деле это фильтр грубой очистки, позволяющий использовать индекс на s_date
.
Assuming you:
Do the following:
first = first row in L
flat_date.start = first.start, flat_date.end = first.end
For each row in L:
if row.start < flat_date.end and row.end > flat_date.end: // adding on to a timespan
flat_date.end = row.end
else: // ending a timespan and starting a new one
add flat_date to F
flat_date.start = row.start, flat_date.end = row.end
add flat_date to F // adding the last timespan to the flattened list
Аналогичный вопрос по SO здесь:
Мин. Срок действия и срок действия для смежных дат
FWIW Я поддержал тот, который рекомендовал Джо Селко SQL для умных людей, третье издание - повторите: Третье издание (2005 г.) - в котором обсуждаются различные подходы, основы и процедуры.
Вот рекурсивное решение CTE, но я взял на себя смелость назначить дату и время каждому столбцу, вместо того, чтобы выводить дату отдельно. Помогает избежать запутанного кода особого случая. Если вы должны хранить дату отдельно, я бы использовал представление CTE, чтобы оно выглядело как два столбца datetime, и пошел бы с этим подходом.
создать тестовые данные:
create table t1 (d1 datetime, d2 datetime)
insert t1 (d1,d2)
select '2009-06-03 10:00:00', '2009-06-03 14:00:00'
union all select '2009-06-03 13:55:00', '2009-06-03 18:00:00'
union all select '2009-06-03 17:55:00', '2009-06-03 23:00:00'
union all select '2009-06-03 22:55:00', '2009-06-04 03:00:00'
union all select '2009-06-04 03:05:00', '2009-06-04 07:00:00'
union all select '2009-06-04 07:05:00', '2009-06-04 10:00:00'
union all select '2009-06-04 09:55:00', '2009-06-04 14:00:00'
Рекурсивный CTE:
;with dateRanges (ancestorD1, parentD1, d2, iter) as
(
--anchor is first level of collapse
select
d1 as ancestorD1,
d1 as parentD1,
d2,
cast(0 as int) as iter
from t1
--recurse as long as there is another range to fold in
union all select
tLeft.ancestorD1,
tRight.d1 as parentD1,
tRight.d2,
iter + 1 as iter
from dateRanges as tLeft join t1 as tRight
--join condition is that the t1 row can be consumed by the recursive row
on tLeft.d2 between tRight.d1 and tRight.d2
--exclude identical rows
and not (tLeft.parentD1 = tRight.d1 and tLeft.d2 = tRight.d2)
)
select
ranges1.*
from dateRanges as ranges1
where not exists (
select 1
from dateRanges as ranges2
where ranges1.ancestorD1 between ranges2.ancestorD1 and ranges2.d2
and ranges1.d2 between ranges2.ancestorD1 and ranges2.d2
and ranges2.iter > ranges1.iter
)
Дает результат:
ancestorD1 parentD1 d2 iter
----------------------- ----------------------- ----------------------- -----------
2009-06-04 03:05:00.000 2009-06-04 03:05:00.000 2009-06-04 07:00:00.000 0
2009-06-04 07:05:00.000 2009-06-04 09:55:00.000 2009-06-04 14:00:00.000 1
2009-06-03 10:00:00.000 2009-06-03 22:55:00.000 2009-06-04 03:00:00.000 3
] Чтобы помочь ответить на вопрос, вот пример данных, приведенных в вопросе в табличной переменной, такой как Hainstech:
declare @T1 table (d1 datetime, d2 datetime)
insert @T1 (d1,d2)
select '02 June 2009 05:55:28','02 June 2009 09:58:27'
union all select '02 June 2009 10:15:19','02 June 2009 13:58:24'
union all select '02 June 2009 13:58:24','02 June 2009 13:58:43'
union all select '03 June 2009 05:54:48','03 June 2009 10:00:13'
union all select '03 June 2009 09:26:45','03 June 2009 09:59:40'
union all select '03 June 2009 10:12:50','03 June 2009 10:27:25'
union all select '03 June 2009 10:13:12','03 June 2009 11:14:56'
union all select '03 June 2009 10:27:25','03 June 2009 10:27:31'
union all select '03 June 2009 10:27:39','03 June 2009 13:53:38'
union all select '03 June 2009 11:14:56','03 June 2009 11:15:03'
union all select '03 June 2009 11:15:30','03 June 2009 14:02:14'
union all select '03 June 2009 13:53:38','03 June 2009 13:53:43'
union all select '03 June 2009 14:02:14','03 June 2009 14:02:31'
union all select '04 June 2009 05:48:27','04 June 2009 09:58:59'
union all select '04 June 2009 06:00:00','04 June 2009 09:59:07'
union all select '04 June 2009 10:15:52','04 June 2009 13:54:52'
union all select '04 June 2009 10:16:01','04 June 2009 13:24:20'
union all select '04 June 2009 13:24:20','04 June 2009 13:24:24'
union all select '04 June 2009 13:24:32','04 June 2009 14:00:39'
union all select '04 June 2009 13:54:52','04 June 2009 13:54:58'
union all select '04 June 2009 14:00:39','04 June 2009 14:00:49'
union all select '05 June 2009 05:53:58','05 June 2009 09:59:12'
union all select '05 June 2009 10:16:05','05 June 2009 13:59:08'
union all select '05 June 2009 13:59:08','05 June 2009 13:59:16'
union all select '06 June 2009 06:04:00','06 June 2009 10:00:00'
union all select '06 June 2009 10:16:54','06 June 2009 10:18:40'
union all select '06 June 2009 10:18:40','06 June 2009 10:18:45'
union all select '06 June 2009 10:23:00','06 June 2009 13:57:00'
union all select '06 June 2009 10:23:48','06 June 2009 13:57:54'
union all select '06 June 2009 13:57:21','06 June 2009 13:57:38'
union all select '06 June 2009 13:57:54','06 June 2009 13:57:58'
union all select '07 June 2009 21:59:30','07 June 2009 01:58:49'
union all select '07 June 2009 22:12:16','07 June 2009 01:58:39'
union all select '07 June 2009 22:12:25','07 June 2009 01:58:28'
union all select '08 June 2009 02:10:33','08 June 2009 05:56:11'
union all select '08 June 2009 02:10:43','08 June 2009 05:56:23'
union all select '08 June 2009 02:10:49','08 June 2009 05:55:59'
union all select '08 June 2009 05:55:59','08 June 2009 05:56:01'
union all select '08 June 2009 05:56:11','08 June 2009 05:56:14'
union all select '08 June 2009 05:56:23','08 June 2009 05:56:27'