查找 T-SQL 中的最大时间重叠
Finding the largest time overlap in T-SQL
我正尝试在 SQL Server 2008 R2 上执行此操作。
我有一个有 4 列的 table:
parent_id INT
child_id INT
start_time TIME
end_time TIME
您应该将 children 视为 sub-processes,将 运行 视为 parent 程序。所有这些 sub-processes 都是每天 运行 一次,每个 child 运行 在其给定的时间跨度内。我想根据其 children 的时间为每个 parent 找到最大的时间间隔重叠,即我想知道所有 sub-processes 都是 运行宁。每个时间跨度每天重复的事实意味着,即使 child 的时间间隔跨越午夜(即 23:00-10:00),它也可以与仅 child 重叠运行 早上(即 07:00-09:00),因为即使它们在 "the first day" 上不重叠,它们也会在随后的所有日子里重叠。
输出应如下所示:
parent_id INT
start_time TIME
end_time TIME
valid BIT
其中 valid = 1
如果发现重叠,valid = 0
如果没有发现重叠。
一些重要信息:
- 时间间隔可以跨越午夜,即
start_time = 23:00
和end_time = 03:00
,即4小时的时间间隔。
- 两个时间间隔可能在两个不同的地方重叠,即
start_time1 = 13:00
、end_time1 = 06:00
、start_time2 = 04:00
、end_time2 = 14:00
。这将给出最大重叠 04:00 - 06:00 = 2 小时。
- 给定 parent 的 children 可能没有共同的重叠,在这种情况下 parent 的输出将是
start_time = NULL
,end_time = NULL
和 valid = 0
.
- 如果 child 间隔跨越一整天,则
start_time = NULL
和 end_time = NULL
。选择此选项是为了避免将一天设置为 00:00-24:00,这会将跨越午夜的重叠部分一分为二,即下面的 parent 3 最终会出现两个重叠(23:00-24 :00 和 00:00 - 004:00),而不是一个 (23:00-04:00).
- 如果时间间隔由 parent 的所有 children 共享,则重叠只是重叠。
- 一个child的时间跨度永远不能超过24小时。
举个例子:
parent_id child_id start_time end_time
1 1 06:00 14:00
1 2 13:00 09:00
1 3 07:00 09:00
2 1 12:00 17:00
2 2 09:00 11:00
3 1 NULL NULL
3 2 23:00 04:00
4 1 NULL NULL
4 2 NULL NULL
10 1 06:11 14:00
10 2 06:00 09:00
10 3 05:00 08:44
11 1 11:38 17:00
11 2 09:02 12:11
这些数据将产生这个结果集:
parent_id start_time end_time valid
1 07:00 09:00 1
2 NULL NULL 0
3 23:00 04:00 1
4 NULL NULL 1
10 06:11 08:44 1
11 11:38 12:11 1
parent 的重叠是其所有 children 共享的时间间隔。因此 parent 10 的重叠是通过找到所有 3 children 共享时间的重叠来找到的:
Child 1 (06:11-14:00) 和 2 (06:00-09:00) 从 06:11 重叠到 09:00。然后将此重叠时间间隔应用于 child 3 (05:00-08:44),这会给出 06:11 到 08:44 的重叠,因为此间隔是唯一的间隔所有 3 children 共享共同时间。
我希望这是有道理的。
我可以用游标来做,但我真的更愿意避免使用游标。我一直在绞尽脑汁思考如何在没有光标的情况下做到这一点,但我做空了。有没有不用游标的方法?
编辑:扩展了第 4 条的文本,以解释将一整天从 NULL 改为 NULL 而不是 00:00 到 00:00 的决定。
编辑:用另外两个案例扩展示例。新案例的 ID 为 parent 10 和 11。
编辑:插入解释如何找到 parent 10 的重叠。
编辑:澄清了第 3 条。添加了第 5 条和第 6 条。详细说明了这一切。
这可能是实现预期结果的一种非常冗长的方法,但它适用于给定的数据集,尽管它应该用更大的数据进行测试。
我只是将 table 连接到自身,其中 parent_id
匹配而 child_id
不同,以获得所有可能重叠的时间组合,然后执行一些DATEDIFF
在对输出进行过滤和分组之前计算差异。
如果需要,您可以运行单独进行以下测试和调整:
-- setup initial table
CREATE TABLE #OverlapTable
(
[parent_id] INT ,
[child_id] INT ,
[start_time] TIME ,
[end_time] TIME
);
-- insert dummy data
INSERT INTO #OverlapTable
( [parent_id], [child_id], [start_time], [end_time] )
VALUES ( 1, 1, '06:00', '14:00' ),
( 1, 2, '13:00', '09:00' ),
( 1, 3, '07:00', '09:00' ),
( 2, 1, '12:00', '17:00' ),
( 2, 2, '09:00', '11:00' ),
( 3, 1, NULL, NULL ),
( 3, 2, '23:00', '04:00' ),
( 4, 1, NULL, NULL ),
( 4, 2, NULL, NULL );
-- insert all combinations into a new temp table #Results with overlap calculations
SELECT *
INTO #Results
FROM ( SELECT t1.parent_id ,
t1.start_time ,
t1.end_time ,
t2.start_time AS t2_start_time ,
t2.end_time AS t2_end_time ,
CASE WHEN t1.start_time IS NULL
AND t1.end_time IS NULL THEN 0
WHEN t1.start_time BETWEEN t2.start_time
AND t2.end_time
THEN DATEDIFF(HOUR, t1.start_time, t2.end_time)
WHEN t1.end_time BETWEEN t2.start_time AND t2.end_time
THEN DATEDIFF(HOUR, t2.start_time, t1.end_time)
ELSE NULL
END AS Overlap
FROM #OverlapTable t1
INNER JOIN #OverlapTable t2 ON t2.parent_id = t1.parent_id
AND t2.child_id != t1.child_id
) t
-- SELECT * FROM #Results -- this shows intermediate results
-- filter and group results with the largest overlaps and handle other cases
SELECT DISTINCT
r.parent_id ,
CASE WHEN r.Overlap IS NULL THEN NULL
ELSE CASE WHEN r.start_time IS NULL THEN r.t2_start_time
ELSE r.start_time
END
END start_time ,
CASE WHEN r.Overlap IS NULL THEN NULL
ELSE CASE WHEN r.end_time IS NULL THEN r.t2_end_time
ELSE r.end_time
END
END end_time ,
CASE WHEN r.Overlap IS NULL THEN 0
ELSE 1
END Valid
FROM #Results r
WHERE EXISTS ( SELECT parent_id ,
MAX(Overlap)
FROM #Results
WHERE r.parent_id = parent_id
GROUP BY parent_id
HAVING MAX(Overlap) = r.Overlap
OR ( MAX(Overlap) IS NULL
AND r.Overlap IS NULL
) )
DROP TABLE #Results
DROP TABLE #OverlapTable
希望对您有所帮助。
根据你的问题,我认为你的输出应该是:
parent_id start_time end_time valid
1 07:00 09:00 1
2 NULL NULL 0
3 23:00 04:00 1
4 NULL NULL 1
10 06:11 08:44 1
11 11:38 12:11 1
这是一个基于集合的解决方案:
DECLARE @Times TABLE
(
parent_id INT
,child_id INT
,start_time TIME
,end_time TIME
);
INSERT INTO @Times
VALUES
(1, 1, '06:00', '14:00')
,(1, 2, '13:00', '09:00')
,(1, 3, '07:00', '09:00')
,(2, 1, '12:00', '17:00')
,(2, 2, '09:00', '11:00')
,(3, 1, NULL, NULL)
,(3, 2, '23:00', '04:00')
,(4, 1, NULL, NULL)
,(4, 2, NULL, NULL)
,(10, 1, '06:11', '14:00')
,(10, 2, '06:00', '09:00')
,(10, 3, '05:00', '08:44')
,(11, 1, '11:38', '17:00')
,(11, 2, '09:02', '12:11');
DECLARE @Parents TABLE
(
parent_id INT PRIMARY KEY
,ChildCount INT
)
INSERT INTO @Parents
SELECT
parent_id
,COUNT(DISTINCT child_id) AS ChildCount
FROM
@Times
GROUP BY
parent_id
DECLARE @StartTime DATETIME2 = '00:00'
DECLARE @MinutesInTwoDays INT = 2880
DECLARE @Minutes TABLE(ThisMinute DATETIME2 PRIMARY KEY);
WITH
MinutesCTE AS
(
SELECT
1 AS MinuteNumber
,@StartTime AS ThisMinute
UNION ALL
SELECT
NextMinuteNumber
,NextMinute
FROM MinutesCTE
CROSS APPLY (VALUES(MinuteNumber+1,DATEADD(MINUTE,1,ThisMinute))) NextDates(NextMinuteNumber,NextMinute)
WHERE
NextMinuteNumber <= @MinutesInTwoDays
)
INSERT INTO @Minutes
SELECT ThisMinute FROM MinutesCTE M OPTION (MAXRECURSION 2880);
DECLARE @SharedMinutes TABLE
(
ThisMinute DATETIME2
,parent_id INT
,UNIQUE(ThisMinute,parent_id)
);
WITH TimesCTE AS
(
SELECT
Times.parent_id
,Times.child_id
,CAST(ISNULL(Times.start_time,'00:00') AS datetime2) AS start_time
,
DATEADD
(
DAY
,
CASE
WHEN Times.end_time IS NULL THEN 2
WHEN Times.start_time > Times.end_time THEN 1
ELSE 0
END
,CAST(ISNULL(Times.end_time,'00:00') AS datetime2)
) as end_time
FROM
@Times Times
UNION ALL
SELECT
Times.parent_id
,Times.child_id
,DATEADD(DAY,1,CAST(Times.start_time as datetime2)) AS start_time
,DATEADD(DAY,1,CAST(Times.end_time AS datetime2)) AS end_time
FROM
@Times Times
WHERE
start_time < end_time
)
--Get minutes shared by all children of each parent
INSERT INTO @SharedMinutes
SELECT
M.ThisMinute
,P.parent_id
FROM
@Minutes M
JOIN
TimesCTE T
ON
M.ThisMinute BETWEEN start_time AND end_time
JOIN
@Parents P
ON T.parent_id = P.parent_id
GROUP BY
M.ThisMinute
,P.parent_id
,P.ChildCount
HAVING
COUNT(DISTINCT T.child_id) = P.ChildCount
--get results
SELECT
parent_id
,CAST(CASE WHEN start_time = '1900-01-01' AND end_time = '1900-01-02 23:59' THEN NULL ELSE start_time END AS TIME) AS start_time
,CAST(CASE WHEN start_time = '1900-01-01' AND end_time = '1900-01-02 23:59' THEN NULL ELSE end_time END AS TIME) AS end_time
,valid
FROM
(
SELECT
P.parent_id
,MIN(ThisMinute) AS start_time
,MAX(ThisMinute) AS end_time
,CASE WHEN MAX(ThisMinute) IS NOT NULL THEN 1 ELSE 0 END AS valid
FROM
@Parents P
LEFT JOIN
@SharedMinutes SM
ON P.parent_id = SM.parent_id
GROUP BY
P.parent_id
) Results
您可能会发现您在问题中概述的迭代算法会更有效。但是如果你采用那种方法,我会使用 WHILE 循环而不是游标。
我正尝试在 SQL Server 2008 R2 上执行此操作。
我有一个有 4 列的 table:
parent_id INT
child_id INT
start_time TIME
end_time TIME
您应该将 children 视为 sub-processes,将 运行 视为 parent 程序。所有这些 sub-processes 都是每天 运行 一次,每个 child 运行 在其给定的时间跨度内。我想根据其 children 的时间为每个 parent 找到最大的时间间隔重叠,即我想知道所有 sub-processes 都是 运行宁。每个时间跨度每天重复的事实意味着,即使 child 的时间间隔跨越午夜(即 23:00-10:00),它也可以与仅 child 重叠运行 早上(即 07:00-09:00),因为即使它们在 "the first day" 上不重叠,它们也会在随后的所有日子里重叠。
输出应如下所示:
parent_id INT
start_time TIME
end_time TIME
valid BIT
其中 valid = 1
如果发现重叠,valid = 0
如果没有发现重叠。
一些重要信息:
- 时间间隔可以跨越午夜,即
start_time = 23:00
和end_time = 03:00
,即4小时的时间间隔。 - 两个时间间隔可能在两个不同的地方重叠,即
start_time1 = 13:00
、end_time1 = 06:00
、start_time2 = 04:00
、end_time2 = 14:00
。这将给出最大重叠 04:00 - 06:00 = 2 小时。 - 给定 parent 的 children 可能没有共同的重叠,在这种情况下 parent 的输出将是
start_time = NULL
,end_time = NULL
和valid = 0
. - 如果 child 间隔跨越一整天,则
start_time = NULL
和end_time = NULL
。选择此选项是为了避免将一天设置为 00:00-24:00,这会将跨越午夜的重叠部分一分为二,即下面的 parent 3 最终会出现两个重叠(23:00-24 :00 和 00:00 - 004:00),而不是一个 (23:00-04:00). - 如果时间间隔由 parent 的所有 children 共享,则重叠只是重叠。
- 一个child的时间跨度永远不能超过24小时。
举个例子:
parent_id child_id start_time end_time
1 1 06:00 14:00
1 2 13:00 09:00
1 3 07:00 09:00
2 1 12:00 17:00
2 2 09:00 11:00
3 1 NULL NULL
3 2 23:00 04:00
4 1 NULL NULL
4 2 NULL NULL
10 1 06:11 14:00
10 2 06:00 09:00
10 3 05:00 08:44
11 1 11:38 17:00
11 2 09:02 12:11
这些数据将产生这个结果集:
parent_id start_time end_time valid
1 07:00 09:00 1
2 NULL NULL 0
3 23:00 04:00 1
4 NULL NULL 1
10 06:11 08:44 1
11 11:38 12:11 1
parent 的重叠是其所有 children 共享的时间间隔。因此 parent 10 的重叠是通过找到所有 3 children 共享时间的重叠来找到的: Child 1 (06:11-14:00) 和 2 (06:00-09:00) 从 06:11 重叠到 09:00。然后将此重叠时间间隔应用于 child 3 (05:00-08:44),这会给出 06:11 到 08:44 的重叠,因为此间隔是唯一的间隔所有 3 children 共享共同时间。
我希望这是有道理的。
我可以用游标来做,但我真的更愿意避免使用游标。我一直在绞尽脑汁思考如何在没有光标的情况下做到这一点,但我做空了。有没有不用游标的方法?
编辑:扩展了第 4 条的文本,以解释将一整天从 NULL 改为 NULL 而不是 00:00 到 00:00 的决定。 编辑:用另外两个案例扩展示例。新案例的 ID 为 parent 10 和 11。 编辑:插入解释如何找到 parent 10 的重叠。 编辑:澄清了第 3 条。添加了第 5 条和第 6 条。详细说明了这一切。
这可能是实现预期结果的一种非常冗长的方法,但它适用于给定的数据集,尽管它应该用更大的数据进行测试。
我只是将 table 连接到自身,其中 parent_id
匹配而 child_id
不同,以获得所有可能重叠的时间组合,然后执行一些DATEDIFF
在对输出进行过滤和分组之前计算差异。
如果需要,您可以运行单独进行以下测试和调整:
-- setup initial table
CREATE TABLE #OverlapTable
(
[parent_id] INT ,
[child_id] INT ,
[start_time] TIME ,
[end_time] TIME
);
-- insert dummy data
INSERT INTO #OverlapTable
( [parent_id], [child_id], [start_time], [end_time] )
VALUES ( 1, 1, '06:00', '14:00' ),
( 1, 2, '13:00', '09:00' ),
( 1, 3, '07:00', '09:00' ),
( 2, 1, '12:00', '17:00' ),
( 2, 2, '09:00', '11:00' ),
( 3, 1, NULL, NULL ),
( 3, 2, '23:00', '04:00' ),
( 4, 1, NULL, NULL ),
( 4, 2, NULL, NULL );
-- insert all combinations into a new temp table #Results with overlap calculations
SELECT *
INTO #Results
FROM ( SELECT t1.parent_id ,
t1.start_time ,
t1.end_time ,
t2.start_time AS t2_start_time ,
t2.end_time AS t2_end_time ,
CASE WHEN t1.start_time IS NULL
AND t1.end_time IS NULL THEN 0
WHEN t1.start_time BETWEEN t2.start_time
AND t2.end_time
THEN DATEDIFF(HOUR, t1.start_time, t2.end_time)
WHEN t1.end_time BETWEEN t2.start_time AND t2.end_time
THEN DATEDIFF(HOUR, t2.start_time, t1.end_time)
ELSE NULL
END AS Overlap
FROM #OverlapTable t1
INNER JOIN #OverlapTable t2 ON t2.parent_id = t1.parent_id
AND t2.child_id != t1.child_id
) t
-- SELECT * FROM #Results -- this shows intermediate results
-- filter and group results with the largest overlaps and handle other cases
SELECT DISTINCT
r.parent_id ,
CASE WHEN r.Overlap IS NULL THEN NULL
ELSE CASE WHEN r.start_time IS NULL THEN r.t2_start_time
ELSE r.start_time
END
END start_time ,
CASE WHEN r.Overlap IS NULL THEN NULL
ELSE CASE WHEN r.end_time IS NULL THEN r.t2_end_time
ELSE r.end_time
END
END end_time ,
CASE WHEN r.Overlap IS NULL THEN 0
ELSE 1
END Valid
FROM #Results r
WHERE EXISTS ( SELECT parent_id ,
MAX(Overlap)
FROM #Results
WHERE r.parent_id = parent_id
GROUP BY parent_id
HAVING MAX(Overlap) = r.Overlap
OR ( MAX(Overlap) IS NULL
AND r.Overlap IS NULL
) )
DROP TABLE #Results
DROP TABLE #OverlapTable
希望对您有所帮助。
根据你的问题,我认为你的输出应该是:
parent_id start_time end_time valid
1 07:00 09:00 1
2 NULL NULL 0
3 23:00 04:00 1
4 NULL NULL 1
10 06:11 08:44 1
11 11:38 12:11 1
这是一个基于集合的解决方案:
DECLARE @Times TABLE
(
parent_id INT
,child_id INT
,start_time TIME
,end_time TIME
);
INSERT INTO @Times
VALUES
(1, 1, '06:00', '14:00')
,(1, 2, '13:00', '09:00')
,(1, 3, '07:00', '09:00')
,(2, 1, '12:00', '17:00')
,(2, 2, '09:00', '11:00')
,(3, 1, NULL, NULL)
,(3, 2, '23:00', '04:00')
,(4, 1, NULL, NULL)
,(4, 2, NULL, NULL)
,(10, 1, '06:11', '14:00')
,(10, 2, '06:00', '09:00')
,(10, 3, '05:00', '08:44')
,(11, 1, '11:38', '17:00')
,(11, 2, '09:02', '12:11');
DECLARE @Parents TABLE
(
parent_id INT PRIMARY KEY
,ChildCount INT
)
INSERT INTO @Parents
SELECT
parent_id
,COUNT(DISTINCT child_id) AS ChildCount
FROM
@Times
GROUP BY
parent_id
DECLARE @StartTime DATETIME2 = '00:00'
DECLARE @MinutesInTwoDays INT = 2880
DECLARE @Minutes TABLE(ThisMinute DATETIME2 PRIMARY KEY);
WITH
MinutesCTE AS
(
SELECT
1 AS MinuteNumber
,@StartTime AS ThisMinute
UNION ALL
SELECT
NextMinuteNumber
,NextMinute
FROM MinutesCTE
CROSS APPLY (VALUES(MinuteNumber+1,DATEADD(MINUTE,1,ThisMinute))) NextDates(NextMinuteNumber,NextMinute)
WHERE
NextMinuteNumber <= @MinutesInTwoDays
)
INSERT INTO @Minutes
SELECT ThisMinute FROM MinutesCTE M OPTION (MAXRECURSION 2880);
DECLARE @SharedMinutes TABLE
(
ThisMinute DATETIME2
,parent_id INT
,UNIQUE(ThisMinute,parent_id)
);
WITH TimesCTE AS
(
SELECT
Times.parent_id
,Times.child_id
,CAST(ISNULL(Times.start_time,'00:00') AS datetime2) AS start_time
,
DATEADD
(
DAY
,
CASE
WHEN Times.end_time IS NULL THEN 2
WHEN Times.start_time > Times.end_time THEN 1
ELSE 0
END
,CAST(ISNULL(Times.end_time,'00:00') AS datetime2)
) as end_time
FROM
@Times Times
UNION ALL
SELECT
Times.parent_id
,Times.child_id
,DATEADD(DAY,1,CAST(Times.start_time as datetime2)) AS start_time
,DATEADD(DAY,1,CAST(Times.end_time AS datetime2)) AS end_time
FROM
@Times Times
WHERE
start_time < end_time
)
--Get minutes shared by all children of each parent
INSERT INTO @SharedMinutes
SELECT
M.ThisMinute
,P.parent_id
FROM
@Minutes M
JOIN
TimesCTE T
ON
M.ThisMinute BETWEEN start_time AND end_time
JOIN
@Parents P
ON T.parent_id = P.parent_id
GROUP BY
M.ThisMinute
,P.parent_id
,P.ChildCount
HAVING
COUNT(DISTINCT T.child_id) = P.ChildCount
--get results
SELECT
parent_id
,CAST(CASE WHEN start_time = '1900-01-01' AND end_time = '1900-01-02 23:59' THEN NULL ELSE start_time END AS TIME) AS start_time
,CAST(CASE WHEN start_time = '1900-01-01' AND end_time = '1900-01-02 23:59' THEN NULL ELSE end_time END AS TIME) AS end_time
,valid
FROM
(
SELECT
P.parent_id
,MIN(ThisMinute) AS start_time
,MAX(ThisMinute) AS end_time
,CASE WHEN MAX(ThisMinute) IS NOT NULL THEN 1 ELSE 0 END AS valid
FROM
@Parents P
LEFT JOIN
@SharedMinutes SM
ON P.parent_id = SM.parent_id
GROUP BY
P.parent_id
) Results
您可能会发现您在问题中概述的迭代算法会更有效。但是如果你采用那种方法,我会使用 WHILE 循环而不是游标。