如何计算时间间隔？
How to make calculation on time intervals?
我有一个问题，我解决了它，但是我写了一个很长的过程，我不能确定它涵盖了所有可能的情况。
问题：
如果我有一个主要间隔时间（From A to B）和次要间隔时间（很多或没有）
(`From X to Y AND From X` to Y` AND X`` to Y`` AND ....`)
我想 SUM 我的主要间隔时间 (AB) 的所有部分 次要间隔 分钟 在高效和最少条件下（SQL 服务器过程和 C# 方法）？
例如：如果我的主区间从 02:00 to 10:30
并说一个次要间隔 From 04:00 to 08:00
现在我想要这个结果：((04:00 - 02:00) + (10:30 -08:00))* 60
图表示例：
在第一种情况下，结果将是：
((X-A) + (B-Y)) * 60
如果我有很多次要时期，它会更复杂。
注意：
可能是仅当我必须将主要周期 [A,B] 与最多 的 UNION 进行比较时才会发生次要间隔之间的重叠平行的次级间隔集。第一组必须只包含一个次级间隔，第二组包含（许多或没有）次级间隔。例如在图中比较 [A,B] 到（集2,5) 第一组 (2) 由一个次级间隔组成，第二组 (5) 由三个次级间隔组成。这是最坏的情况，我需要处理。
例如：
如果我的主要间隔是 [15:00,19:40]
我有两组次级间隔。根据我的规则，这些组中至少有一组应该由一个次级间隔组成。
假设第一组是 [11:00 ,16:00]
第二组由两个次要间隔组成 [10:00,15:00],[16:30,17:45]
现在我想要结果 (16:30 -16:00) +(19:40 -17:45)
根据评论：
我的table是这样的:
第一个table包含次要期间，对于特定员工在同一日期最多两组次要期间。第一个集合仅包含工作日 (W) [work_st,work_end] 中的一个次要时段，如果当天是周末 [E] 并且在这种情况下次要时段之间没有重叠，则该集合将为空。第二组可能包含同一日期的许多次要期间 [check_in,check_out] ，因为该员工可能在同一天 check_in_out 多次。
emp_num day_date work_st work_end check_in check_out day_state
547 2015-4-1 08:00 16:00 07:45 12:10 W
547 2015-4-1 08:00 16:00 12:45 17:24 W
547 2015-4-2 00:00 00:00 07:11 13:11 E
第二个 table 包含主要期间[A,B] 并且是该员工当天的一个期间（一条记录）
emp_num day_date mission_in mission_out
547 2015-4-1 15:00 21:30
547 2015-4-2 8:00 14:00
在前面的例子中，如果我有一个需要的过程或方法，这个过程应该有两个参数：
- 日期
- emp_num
在前面的例子中应该是这样的('2015-4-1' ,547)
根据我的解释：
主要时期（Mission Period）[A,B]从第二个table开始：
该员工在此日期中应该只有一个时期
[15:00,21:30]
该员工的已过日期 ('2015-4-1') 的次要期间是两个
从第一个 table
开始的次要时期集（最坏情况）
第一组应仅包含一个次要周期（或零个
periods) [08:00,16:00] 第二组可能包含许多次要的
周期（或零周期）
[07:45,12:10],[12:45,17:24]
The output should be [17:24,21:30] converted to minutes
备注
全部day_date,mission_in,mission_out,work_st,work_end,check_in,check_out
是 datetime 字段，但为了简化，我只在示例中放了时间，我想忽略 day_date 以外的日期部分，因为除了 emp_num 之外，它是我计算的日期].
我不得不解决这个问题来消化一些调度数据。这允许多个在线时间，但假设它们不重叠。
select convert(datetime,'1/1/2015 5:00 AM') StartDateTime, convert(datetime,'1/1/2015 5:00 PM') EndDateTime, convert(varchar(20),'Online') IntervalType into #CapacityIntervals
insert into #CapacityIntervals select '1/1/2015 4:00 AM' StartDateTime, '1/1/2015 6:00 AM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 5:00 AM' StartDateTime, '1/1/2015 6:00 AM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 10:00 AM' StartDateTime, '1/1/2015 12:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 11:00 AM' StartDateTime, '1/1/2015 1:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 4:00 PM' StartDateTime, '1/1/2015 6:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 1:30 PM' StartDateTime, '1/1/2015 2:00 PM' EndDateTime, 'Offline' IntervalType
--Populate your Offline table
select
ROW_NUMBER() over (Order by StartDateTime, EndDateTime) Rownum,
StartDateTime,
EndDateTime
into #Offline
from #CapacityIntervals
where IntervalType in ('Offline','Cleanout')
group by StartDateTime, EndDateTime
--Populate your Online table
select
ROW_NUMBER() over (Order by StartDateTime, EndDateTime) Rownum,
StartDateTime,
EndDateTime
into #Online
from #CapacityIntervals
where IntervalType not in ('Offline','Cleanout')
--If you have overlapping online intervals... check for those here and consolidate.
-------------------------------
--find overlaping offline times
-------------------------------
declare @Finished as tinyint
set @Finished = 0
while @Finished = 0
Begin
update #Offline
set #Offline.EndDateTime = OverlapEndDates.EndDateTime
from #Offline
join
(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum <= Overlap.Rownum
group by #Offline.Rownum
) OverlapEndDates
on #Offline.Rownum = OverlapEndDates.Rownum
--Remove Online times completely inside of online times
delete #Offline
from #Offline
join #Offline Overlap
on #Offline.StartDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.EndDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.Rownum > Overlap.Rownum
--LOOK IF THERE ARE ANY MORE CHAINS LEFT
IF NOT EXISTS(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum < Overlap.Rownum
group by #Offline.Rownum
)
SET @Finished = 1
END
-------------------------------
--Modify Online times with offline ranges
-------------------------------
--delete any Online times completely inside offline range
delete #Online
from #Online
join #Offline
on #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range at the beginning
update #Online
set #Online.StartDateTime = #Offline.EndDateTime
from #Online
join #Offline
on #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime >= #Offline.EndDateTime
--Find Online Times with offline range at the end
update #Online
set #Online.EndDateTime = #Offline.StartDateTime
from #Online
join #Offline
on #Online.StartDateTime <= #Offline.StartDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range punched in the middle
select #Online.Rownum,
#Offline.Rownum OfflineRow,
#Offline.StartDateTime,
#Offline.EndDateTime,
ROW_NUMBER() over (Partition by #Online.Rownum order by #Offline.Rownum Desc) OfflineHoleNumber
into #OfflineHoles
from #Online
join #Offline
on #Offline.StartDateTime between #Online.StartDateTime and #Online.EndDateTime
and #Offline.EndDateTime between #Online.StartDateTime and #Online.EndDateTime
declare @HoleNumber as integer
select @HoleNumber = isnull(MAX(OfflineHoleNumber),0) from #OfflineHoles
--Punch the holes out of the online times
While @HoleNumber > 0
Begin
insert into #Online
select
-1 Rownum,
#OfflineHoles.EndDateTime StartDateTime,
#Online.EndDateTime EndDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
update #Online
set #Online.EndDateTime = #OfflineHoles.StartDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
set @HoleNumber=@HoleNumber-1
end
--Output total hours
select SUM(datediff(second,StartDateTime, EndDateTime)) / 3600.0 TotalHr
from #Online
--see how it split up the online intervals
select *
from #Online
order by StartDateTime, EndDateTime
我已经用您的数据示例更新了我的答案，并且我正在为使用您图表中的案例 2 和案例 5 的员工 248 添加另一个示例。
--load example data for emply 547
select CONVERT(int, 547) emp_num,
Convert(datetime, '2015-4-1') day_date,
Convert(datetime, '2015-4-1 08:00') work_st,
Convert(datetime, '2015-4-1 16:00') work_end,
Convert(datetime, '2015-4-1 07:45') check_in,
Convert(datetime, '2015-4-1 12:10') check_out,
'W' day_state
into #SecondaryIntervals
insert into #SecondaryIntervals select 547, '2015-4-1', '2015-4-1 08:00', '2015-4-1 16:00', '2015-4-1 12:45', '2015-4-1 17:24', 'W'
insert into #SecondaryIntervals select 547, '2015-4-2', '2015-4-2 00:00', '2015-4-2 00:00', '2015-4-2 07:11', '2015-4-2 13:11', 'E'
select CONVERT(int, 547) emp_num,
Convert(datetime, '2015-4-1') day_date,
Convert(datetime, '2015-4-1 15:00') mission_in,
Convert(datetime, '2015-4-1 21:30') mission_out
into #MainIntervals
insert into #MainIntervals select 547, '2015-4-2', '2015-4-2 8:00', '2015-4-2 14:00'
--load more example data for an employee 548 with overlapping secondary intervals
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 9:00', '2015-4-1 10:00', 'W'
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 10:30', '2015-4-1 12:30', 'W'
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 13:15', '2015-4-1 16:00', 'W'
insert into #MainIntervals select 548, '2015-4-1', '2015-4-1 8:00', '2015-4-1 14:00'
--Populate your Offline table with the intervals in #SecondaryIntervals
select
ROW_NUMBER() over (Order by emp_num, day_date, StartDateTime, EndDateTime) Rownum,
emp_num,
day_date,
StartDateTime,
EndDateTime
into #Offline
from
(select emp_num,
day_date,
work_st StartDateTime,
work_end EndDateTime
from #SecondaryIntervals
where day_state = 'W'
Group by emp_num,
day_date,
work_st,
work_end
union
select
emp_num,
day_date,
check_in StartDateTime,
check_out EndDateTime
from #SecondaryIntervals
Group by emp_num,
day_date,
check_in,
check_out
) SecondaryIntervals
--Populate your Online table
select
ROW_NUMBER() over (Order by emp_num, day_date, mission_in, mission_out) Rownum,
emp_num,
day_date,
mission_in StartDateTime,
mission_out EndDateTime
into #Online
from #MainIntervals
group by emp_num,
day_date,
mission_in,
mission_out
-------------------------------
--find overlaping offline times
-------------------------------
declare @Finished as tinyint
set @Finished = 0
while @Finished = 0
Begin
update #Offline
set #Offline.EndDateTime = OverlapEndDates.EndDateTime
from #Offline
join
(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum <= Overlap.Rownum
group by #Offline.Rownum
) OverlapEndDates
on #Offline.Rownum = OverlapEndDates.Rownum
--Remove Online times completely inside of online times
delete #Offline
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and #Offline.StartDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.EndDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.Rownum > Overlap.Rownum
--LOOK IF THERE ARE ANY MORE CHAINS LEFT
IF NOT EXISTS(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum < Overlap.Rownum
group by #Offline.Rownum
)
SET @Finished = 1
END
-------------------------------
--Modify Online times with offline ranges
-------------------------------
--delete any Online times completely inside offline range
delete #Online
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range at the beginning
update #Online
set #Online.StartDateTime = #Offline.EndDateTime
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime >= #Offline.EndDateTime
--Find Online Times with offline range at the end
update #Online
set #Online.EndDateTime = #Offline.StartDateTime
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime <= #Offline.StartDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range punched in the middle
select #Online.Rownum,
#Offline.Rownum OfflineRow,
#Offline.StartDateTime,
#Offline.EndDateTime,
ROW_NUMBER() over (Partition by #Online.Rownum order by #Offline.Rownum Desc) OfflineHoleNumber
into #OfflineHoles
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Offline.StartDateTime between #Online.StartDateTime and #Online.EndDateTime
and #Offline.EndDateTime between #Online.StartDateTime and #Online.EndDateTime
declare @HoleNumber as integer
select @HoleNumber = isnull(MAX(OfflineHoleNumber),0) from #OfflineHoles
--Punch the holes out of the online times
While @HoleNumber > 0
Begin
insert into #Online
select
-1 Rownum,
#Online.emp_num,
#Online.day_date,
#OfflineHoles.EndDateTime StartDateTime,
#Online.EndDateTime EndDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
update #Online
set #Online.EndDateTime = #OfflineHoles.StartDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
set @HoleNumber=@HoleNumber-1
end
--Output total hours
select emp_num, day_date,
SUM(datediff(second,StartDateTime, EndDateTime)) / 3600.0 TotalHr,
SUM(datediff(second,StartDateTime, EndDateTime)) / 60.0 TotalMin
from #Online
group by emp_num, day_date
order by 1, 2
--see how it split up the online intervals
select emp_num, day_date, StartDateTime, EndDateTime
from #Online
order by 1, 2, 3, 4
输出为：
emp_num day_date TotalHr TotalMin
----------- ----------------------- --------------------------------------- ---------------------------------------
547 2015-04-01 00:00:00.000 4.100000 246.000000
547 2015-04-02 00:00:00.000 0.816666 49.000000
548 2015-04-01 00:00:00.000 0.750000 45.000000
(3 row(s) affected)
emp_num day_date StartDateTime EndDateTime
----------- ----------------------- ----------------------- -----------------------
547 2015-04-01 00:00:00.000 2015-04-01 17:24:00.000 2015-04-01 21:30:00.000
547 2015-04-02 00:00:00.000 2015-04-02 13:11:00.000 2015-04-02 14:00:00.000
548 2015-04-01 00:00:00.000 2015-04-01 12:30:00.000 2015-04-01 13:15:00.000
(3 row(s) affected)
我留下了我的另一个答案，因为它更通用，以防其他人想抢走它。我看到你给这个问题加了赏金。让我知道我的回答中是否有某些具体内容不能让您满意，我会尽力帮助您。我用这种方法处理了数千个间隔，它 returns 只需几秒钟。
这里是 SQLFiddle 完整的查询。
我将展示如何构建一个查询，每个 emp_num, day_date 分钟数 returns。如果事实证明特定 emp_num, day_date 没有分钟剩余，那么结果将 没有 与 0 的行，根本没有这样的行.
总体思路
我会用一个table of numbers. We'll need only 24*60=1440 numbers, but it is a good idea to have such table in your database for other reports. I personally have it with 100,000 rows. Here is a very good article比较不同的方法来生成这样的table。
对于每个间隔，我将使用 table 的数字生成一组行 - 间隔中的每一分钟一行。我假设间隔是 [start; end)，即开始分钟包括在内，结束分钟不包括在内。例如，从 07:00 到 08:00 的间隔是 60 分钟，而不是 61.
生成 table 个数字
DECLARE @Numbers TABLE (N int);
INSERT INTO @Numbers(N)
SELECT TOP(24*60)
ROW_NUMBER() OVER(ORDER BY S.object_id) - 1 AS N
FROM
sys.all_objects AS S
ORDER BY N
;
对于此任务，最好使用从 0 开始的数字。通常您会将其作为永久 table，主键位于 N。
样本数据
DECLARE @Missions TABLE (emp_num int, day_date datetime, mission_in datetime, mission_out datetime);
DECLARE @Periods TABLE (emp_num int, day_date datetime, work_st datetime, work_end datetime, check_in datetime, check_out datetime, day_state char(1));
INSERT INTO @Missions (emp_num, day_date, mission_in, mission_out) VALUES
(547, '2015-04-01', '2015-04-01 15:00:00', '2015-04-01 21:30:00'),
(547, '2015-04-02', '2015-04-02 08:00:00', '2015-04-02 14:00:00');
INSERT INTO @Periods (emp_num, day_date, work_st, work_end, check_in, check_out, day_state) VALUES
(547, '2015-04-01', '2015-04-01 08:00:00', '2015-04-01 16:00:00', '2015-04-01 07:45:00', '2015-04-01 12:10:00', 'W'),
(547, '2015-04-01', '2015-04-01 08:00:00', '2015-04-01 16:00:00', '2015-04-01 12:45:00', '2015-04-01 17:24:00', 'W'),
(547, '2015-04-02', '2015-04-02 00:00:00', '2015-04-02 00:00:00', '2015-04-02 07:11:00', '2015-04-02 13:11:00', 'E');
我的解决方案不会使用 day_state 列。我希望您对 work_st 和 work_end 都有 00:00:00。解决方案要求同一行中的日期组件相同，并且 day_date 没有时间组件。
如果我为此任务设计架构，我将有三个 table 而不是两个：Missions、WorkPeriods 和 CheckPeriods。我会将您的 table Periods 分成两部分，以避免在多行中重复 work_st 和 work_end。但是这个解决方案将处理您当前的架构，并且它实际上会即时生成第三个 table。实际上，这意味着性能可能会有所提高。
任务分钟数
WITH
CTE_MissionMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
@Missions AS M
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, M.day_date, M.mission_in) AND
N.N < DATEDIFF(minute, M.day_date, M.mission_out)
)
@Missions 中的每个原始行变成一组行，间隔 (mission_in, mission_out) 的每一分钟一个。
工作时间
,CTE_WorkPeriods
AS
(
SELECT P.emp_num, P.day_date, P.work_st, P.work_end
FROM @Periods AS P
GROUP BY P.emp_num, P.day_date, P.work_st, P.work_end
)
生成第三个助手 table - 每个 emp_num, day_date, work_st, work_end 一行 - (work_st, work_end) 的所有间隔。
工作和检查分钟数
,CTE_WorkMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
CTE_WorkPeriods
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, CTE_WorkPeriods.day_date, CTE_WorkPeriods.work_st) AND
N.N < DATEDIFF(minute, CTE_WorkPeriods.day_date, CTE_WorkPeriods.work_end)
)
,CTE_CheckMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
@Periods AS P
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, P.day_date, P.check_in) AND
N.N < DATEDIFF(minute, P.day_date, P.check_out)
)
与 Missions 完全相同。
联盟"secondary intervals"
,CTE_UnionPeriodMinutes
AS
(
SELECT emp_num, day_date, N
FROM CTE_WorkMinutes
UNION ALL -- can be not ALL here, but ALL is usually faster
SELECT emp_num, day_date, N
FROM CTE_CheckMinutes
)
从主要间隔中减去次要间隔
,CTE_FinalMinutes
AS
(
SELECT emp_num, day_date, N
FROM CTE_MissionMinutes
EXCEPT
SELECT emp_num, day_date, N
FROM CTE_UnionPeriodMinutes
)
总结分钟数
SELECT
emp_num
,day_date
,COUNT(*) AS FinalMinutes
FROM CTE_FinalMinutes
GROUP BY emp_num, day_date
ORDER BY emp_num, day_date;
要进行最终查询，只需将所有 CTE 放在一起即可。
结果集
emp_num day_date FinalMinutes
547 2015-04-01 00:00:00.000 246
547 2015-04-02 00:00:00.000 49
There are 246 minutes between 17:24 and 21:30.
There are 49 minutes between 13:11 and 14:00.
这里是 SQLFiddle 完整的查询。
显示导致此 SUM 分钟的实际间隔相当容易，但您说您只需要 SUM.
我的解决方案与 Vladimir Baranov 非常相似。
Link 到 .NetFiddle
总体思路
我的算法基于 interval tree 的修改。假设最小时间单位为1分钟（易于修改）。
每个树节点处于 3 种状态之一：未访问、已访问和已使用。该算法基于递归 Search 函数，可通过以下步骤描述：
- 如果节点已使用或搜索区间为空则return空区间。
- 如果节点未访问且节点间隔等于搜索间隔，则将当前节点标记为已使用和return节点间隔。
- 将节点标记为已访问，拆分搜索间隔和 return 左右子节点 Search 的总和。
解决步骤
- 计算最大区间。
- 添加到树 "secondary intervals"。
- 添加到树 "main interval"。
计算间隔总和。
请注意 我假设间隔是 [start; end]，即两个区间都包含在内，容易改变。
要求
假设
n - "secondary intervals"
的数量
米 - 基本单位的最大时间
构造需要 O(2n) 存储 space 并在 O(n log n + m) 时间内工作。
这是我的代码
public class Interval
{
public int Start { get; set; }
public int End { get; set; }
};
enum Node
{
Unvisited = 0,
Visited = 1,
Used = 2
};
Node[] tree;
public void Calculate()
{
var secondryIntervalsAsDates = new List<Tuple<DateTime,DateTime>> { new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 0, 0), new DateTime(2015, 03, 15, 5, 0, 0))};
var mainInvtervalAsDate = new Tuple<DateTime, DateTime>(new DateTime(2015, 03, 15, 3, 0, 0), new DateTime(2015, 03, 15, 7, 0, 0));
// calculate biggest interval
var startDate = secondryIntervalsAsDates.Union( new List<Tuple<DateTime,DateTime>>{mainInvtervalAsDate}).Min(s => s.Item1).AddMinutes(-1);
var endDate = secondryIntervalsAsDates.Union(new List<Tuple<DateTime, DateTime>> { mainInvtervalAsDate }).Max(s => s.Item2);
var mainInvterval = new Interval { Start = (int)(mainInvtervalAsDate.Item1 - startDate).TotalMinutes, End = (int)(mainInvtervalAsDate.Item2 - startDate).TotalMinutes };
var wholeInterval = new Interval { Start = 1, End = (int)(endDate - startDate).TotalMinutes};
//convert intervals to minutes
var secondaryIntervals = secondryIntervalsAsDates.Select(s => new Interval { Start = (int)(s.Item1 - startDate).TotalMinutes, End = (int)(s.Item2 - startDate).TotalMinutes}).ToList();
tree = new Node[wholeInterval.End * 2 + 1];
//insert secondary intervals
secondaryIntervals.ForEach(s => Search(wholeInterval, s, 1));
//insert main interval
var result = Search(wholeInterval, mainInvterval, 1);
//calculate result
var minutes = result.Sum(r => r.End - r.Start) + result.Count();
}
public IEnumerable<Interval> Search(Interval current, Interval searching, int index)
{
if (tree[index] == Node.Used || searching.End < searching.Start)
{
return new List<Interval>();
}
if (tree[index] == Node.Unvisited && current.Start == searching.Start && current.End == searching.End)
{
tree[index] = Node.Used;
return new List<Interval> { current };
}
tree[index] = Node.Visited;
return Search(new Interval { Start = current.Start, End = current.Start + (current.End - current.Start) / 2 },
new Interval { Start = searching.Start, End = Math.Min(searching.End, current.Start + (current.End - current.Start) / 2) }, index * 2).Union(
Search(new Interval { Start = current.Start + (current.End - current.Start) / 2 + 1 , End = current.End},
new Interval { Start = Math.Max(searching.Start, current.Start + (current.End - current.Start) / 2 + 1), End = searching.End }, index * 2 + 1));
}
我找到了可能是最简单的解决方案。
- 按开始日期排序 "Secondary intervals"。
- 寻找 "secondary intervals" 中的空白（简单迭代）
与"main interval"比较差距。
//declare intervals
var secondryIntervals = new List<Tuple<DateTime, DateTime>> {
new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 0, 0), new DateTime(2015, 03, 15, 5, 0, 0)),
new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 10, 0), new DateTime(2015, 03, 15, 4, 40, 0)),
new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 40, 0), new DateTime(2015, 03, 15, 5, 20, 0))};
var mainInterval = new Tuple<DateTime, DateTime>(new DateTime(2015, 03, 15, 3, 0, 0), new DateTime(2015, 03, 15, 7, 0, 0));
// add two empty intervals before and after main interval
secondryIntervals.Add(new Tuple<DateTime, DateTime>(mainInterval.Item1.AddMinutes(-1), mainInterval.Item1.AddMinutes(-1)));
secondryIntervals.Add(new Tuple<DateTime, DateTime>(mainInterval.Item2.AddMinutes(1), mainInterval.Item2.AddMinutes(1)));
secondryIntervals = secondryIntervals.OrderBy(s => s.Item1).ToList();
// endDate will rember 'biggest' end date
var endDate = secondryIntervals.First().Item1;
var result = secondryIntervals.Select(s =>
{
var temp = endDate;
endDate = endDate < s.Item2 ? s.Item2 : endDate;
if (s.Item1 > temp)
{
return new Tuple<DateTime, DateTime>(temp < mainInterval.Item1 ? mainInterval.Item1 : temp,
mainInterval.Item2 < s.Item1 ? mainInterval.Item2 : s.Item1);
}
return null;
})
// remove empty records
.Where(s => s != null && s.Item2 > s.Item1).ToList();
var minutes = result.Sum(s => (s.Item2 - s.Item1).TotalMinutes);
该算法需要 O(n log n) 时间（用于排序）而无需额外的存储和假设。
我有一个问题，我解决了它，但是我写了一个很长的过程，我不能确定它涵盖了所有可能的情况。
问题：
如果我有一个主要间隔时间（From A to B）和次要间隔时间（很多或没有）
(`From X to Y AND From X` to Y` AND X`` to Y`` AND ....`)
我想 SUM 我的主要间隔时间 (AB) 的所有部分 次要间隔 分钟 在高效和最少条件下（SQL 服务器过程和 C# 方法）？
例如：如果我的主区间从 02:00 to 10:30
并说一个次要间隔 From 04:00 to 08:00
现在我想要这个结果：((04:00 - 02:00) + (10:30 -08:00))* 60
图表示例：
在第一种情况下，结果将是：
((X-A) + (B-Y)) * 60
如果我有很多次要时期，它会更复杂。
注意：
可能是仅当我必须将主要周期 [A,B] 与最多 的 UNION 进行比较时才会发生次要间隔之间的重叠平行的次级间隔集。第一组必须只包含一个次级间隔，第二组包含（许多或没有）次级间隔。例如在图中比较 [A,B] 到（集2,5) 第一组 (2) 由一个次级间隔组成，第二组 (5) 由三个次级间隔组成。这是最坏的情况，我需要处理。
例如：
如果我的主要间隔是 [15:00,19:40]
我有两组次级间隔。根据我的规则，这些组中至少有一组应该由一个次级间隔组成。
假设第一组是 [11:00 ,16:00]
第二组由两个次要间隔组成 [10:00,15:00],[16:30,17:45]
现在我想要结果 (16:30 -16:00) +(19:40 -17:45)
根据评论：
我的table是这样的:
第一个table包含次要期间，对于特定员工在同一日期最多两组次要期间。第一个集合仅包含工作日 (W) [work_st,work_end] 中的一个次要时段，如果当天是周末 [E] 并且在这种情况下次要时段之间没有重叠，则该集合将为空。第二组可能包含同一日期的许多次要期间 [check_in,check_out] ，因为该员工可能在同一天 check_in_out 多次。
emp_num day_date work_st work_end check_in check_out day_state
547 2015-4-1 08:00 16:00 07:45 12:10 W
547 2015-4-1 08:00 16:00 12:45 17:24 W
547 2015-4-2 00:00 00:00 07:11 13:11 E
第二个 table 包含主要期间[A,B] 并且是该员工当天的一个期间（一条记录）
emp_num day_date mission_in mission_out
547 2015-4-1 15:00 21:30
547 2015-4-2 8:00 14:00
在前面的例子中，如果我有一个需要的过程或方法，这个过程应该有两个参数：
- 日期
- emp_num
在前面的例子中应该是这样的('2015-4-1' ,547)
根据我的解释：
主要时期（Mission Period）
[A,B]从第二个table开始： 该员工在此日期中应该只有一个时期[15:00,21:30]该员工的已过日期
开始的次要时期集（最坏情况）('2015-4-1')的次要期间是两个 从第一个 table第一组应仅包含一个次要周期（或零个 periods)
[08:00,16:00]第二组可能包含许多次要的 周期（或零周期）[07:45,12:10],[12:45,17:24]
The output should be [17:24,21:30] converted to minutes
备注
全部day_date,mission_in,mission_out,work_st,work_end,check_in,check_out
是 datetime 字段，但为了简化，我只在示例中放了时间，我想忽略 day_date 以外的日期部分，因为除了 emp_num 之外，它是我计算的日期].
我不得不解决这个问题来消化一些调度数据。这允许多个在线时间，但假设它们不重叠。
select convert(datetime,'1/1/2015 5:00 AM') StartDateTime, convert(datetime,'1/1/2015 5:00 PM') EndDateTime, convert(varchar(20),'Online') IntervalType into #CapacityIntervals
insert into #CapacityIntervals select '1/1/2015 4:00 AM' StartDateTime, '1/1/2015 6:00 AM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 5:00 AM' StartDateTime, '1/1/2015 6:00 AM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 10:00 AM' StartDateTime, '1/1/2015 12:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 11:00 AM' StartDateTime, '1/1/2015 1:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 4:00 PM' StartDateTime, '1/1/2015 6:00 PM' EndDateTime, 'Offline' IntervalType
insert into #CapacityIntervals select '1/1/2015 1:30 PM' StartDateTime, '1/1/2015 2:00 PM' EndDateTime, 'Offline' IntervalType
--Populate your Offline table
select
ROW_NUMBER() over (Order by StartDateTime, EndDateTime) Rownum,
StartDateTime,
EndDateTime
into #Offline
from #CapacityIntervals
where IntervalType in ('Offline','Cleanout')
group by StartDateTime, EndDateTime
--Populate your Online table
select
ROW_NUMBER() over (Order by StartDateTime, EndDateTime) Rownum,
StartDateTime,
EndDateTime
into #Online
from #CapacityIntervals
where IntervalType not in ('Offline','Cleanout')
--If you have overlapping online intervals... check for those here and consolidate.
-------------------------------
--find overlaping offline times
-------------------------------
declare @Finished as tinyint
set @Finished = 0
while @Finished = 0
Begin
update #Offline
set #Offline.EndDateTime = OverlapEndDates.EndDateTime
from #Offline
join
(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum <= Overlap.Rownum
group by #Offline.Rownum
) OverlapEndDates
on #Offline.Rownum = OverlapEndDates.Rownum
--Remove Online times completely inside of online times
delete #Offline
from #Offline
join #Offline Overlap
on #Offline.StartDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.EndDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.Rownum > Overlap.Rownum
--LOOK IF THERE ARE ANY MORE CHAINS LEFT
IF NOT EXISTS(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum < Overlap.Rownum
group by #Offline.Rownum
)
SET @Finished = 1
END
-------------------------------
--Modify Online times with offline ranges
-------------------------------
--delete any Online times completely inside offline range
delete #Online
from #Online
join #Offline
on #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range at the beginning
update #Online
set #Online.StartDateTime = #Offline.EndDateTime
from #Online
join #Offline
on #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime >= #Offline.EndDateTime
--Find Online Times with offline range at the end
update #Online
set #Online.EndDateTime = #Offline.StartDateTime
from #Online
join #Offline
on #Online.StartDateTime <= #Offline.StartDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range punched in the middle
select #Online.Rownum,
#Offline.Rownum OfflineRow,
#Offline.StartDateTime,
#Offline.EndDateTime,
ROW_NUMBER() over (Partition by #Online.Rownum order by #Offline.Rownum Desc) OfflineHoleNumber
into #OfflineHoles
from #Online
join #Offline
on #Offline.StartDateTime between #Online.StartDateTime and #Online.EndDateTime
and #Offline.EndDateTime between #Online.StartDateTime and #Online.EndDateTime
declare @HoleNumber as integer
select @HoleNumber = isnull(MAX(OfflineHoleNumber),0) from #OfflineHoles
--Punch the holes out of the online times
While @HoleNumber > 0
Begin
insert into #Online
select
-1 Rownum,
#OfflineHoles.EndDateTime StartDateTime,
#Online.EndDateTime EndDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
update #Online
set #Online.EndDateTime = #OfflineHoles.StartDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
set @HoleNumber=@HoleNumber-1
end
--Output total hours
select SUM(datediff(second,StartDateTime, EndDateTime)) / 3600.0 TotalHr
from #Online
--see how it split up the online intervals
select *
from #Online
order by StartDateTime, EndDateTime
我已经用您的数据示例更新了我的答案，并且我正在为使用您图表中的案例 2 和案例 5 的员工 248 添加另一个示例。
--load example data for emply 547
select CONVERT(int, 547) emp_num,
Convert(datetime, '2015-4-1') day_date,
Convert(datetime, '2015-4-1 08:00') work_st,
Convert(datetime, '2015-4-1 16:00') work_end,
Convert(datetime, '2015-4-1 07:45') check_in,
Convert(datetime, '2015-4-1 12:10') check_out,
'W' day_state
into #SecondaryIntervals
insert into #SecondaryIntervals select 547, '2015-4-1', '2015-4-1 08:00', '2015-4-1 16:00', '2015-4-1 12:45', '2015-4-1 17:24', 'W'
insert into #SecondaryIntervals select 547, '2015-4-2', '2015-4-2 00:00', '2015-4-2 00:00', '2015-4-2 07:11', '2015-4-2 13:11', 'E'
select CONVERT(int, 547) emp_num,
Convert(datetime, '2015-4-1') day_date,
Convert(datetime, '2015-4-1 15:00') mission_in,
Convert(datetime, '2015-4-1 21:30') mission_out
into #MainIntervals
insert into #MainIntervals select 547, '2015-4-2', '2015-4-2 8:00', '2015-4-2 14:00'
--load more example data for an employee 548 with overlapping secondary intervals
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 9:00', '2015-4-1 10:00', 'W'
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 10:30', '2015-4-1 12:30', 'W'
insert into #SecondaryIntervals select 548, '2015-4-1', '2015-4-1 06:00', '2015-4-1 11:00', '2015-4-1 13:15', '2015-4-1 16:00', 'W'
insert into #MainIntervals select 548, '2015-4-1', '2015-4-1 8:00', '2015-4-1 14:00'
--Populate your Offline table with the intervals in #SecondaryIntervals
select
ROW_NUMBER() over (Order by emp_num, day_date, StartDateTime, EndDateTime) Rownum,
emp_num,
day_date,
StartDateTime,
EndDateTime
into #Offline
from
(select emp_num,
day_date,
work_st StartDateTime,
work_end EndDateTime
from #SecondaryIntervals
where day_state = 'W'
Group by emp_num,
day_date,
work_st,
work_end
union
select
emp_num,
day_date,
check_in StartDateTime,
check_out EndDateTime
from #SecondaryIntervals
Group by emp_num,
day_date,
check_in,
check_out
) SecondaryIntervals
--Populate your Online table
select
ROW_NUMBER() over (Order by emp_num, day_date, mission_in, mission_out) Rownum,
emp_num,
day_date,
mission_in StartDateTime,
mission_out EndDateTime
into #Online
from #MainIntervals
group by emp_num,
day_date,
mission_in,
mission_out
-------------------------------
--find overlaping offline times
-------------------------------
declare @Finished as tinyint
set @Finished = 0
while @Finished = 0
Begin
update #Offline
set #Offline.EndDateTime = OverlapEndDates.EndDateTime
from #Offline
join
(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum <= Overlap.Rownum
group by #Offline.Rownum
) OverlapEndDates
on #Offline.Rownum = OverlapEndDates.Rownum
--Remove Online times completely inside of online times
delete #Offline
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and #Offline.StartDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.EndDateTime between Overlap.StartDateTime and Overlap.EndDateTime
and #Offline.Rownum > Overlap.Rownum
--LOOK IF THERE ARE ANY MORE CHAINS LEFT
IF NOT EXISTS(
select #Offline.Rownum,
MAX(Overlap.EndDateTime) EndDateTime
from #Offline
join #Offline Overlap
on #Offline.emp_num = Overlap.emp_num
and #Offline.day_date = Overlap.day_date
and Overlap.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Offline.Rownum < Overlap.Rownum
group by #Offline.Rownum
)
SET @Finished = 1
END
-------------------------------
--Modify Online times with offline ranges
-------------------------------
--delete any Online times completely inside offline range
delete #Online
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range at the beginning
update #Online
set #Online.StartDateTime = #Offline.EndDateTime
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime between #Offline.StartDateTime and #Offline.EndDateTime
and #Online.EndDateTime >= #Offline.EndDateTime
--Find Online Times with offline range at the end
update #Online
set #Online.EndDateTime = #Offline.StartDateTime
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Online.StartDateTime <= #Offline.StartDateTime
and #Online.EndDateTime between #Offline.StartDateTime and #Offline.EndDateTime
--Find Online Times with offline range punched in the middle
select #Online.Rownum,
#Offline.Rownum OfflineRow,
#Offline.StartDateTime,
#Offline.EndDateTime,
ROW_NUMBER() over (Partition by #Online.Rownum order by #Offline.Rownum Desc) OfflineHoleNumber
into #OfflineHoles
from #Online
join #Offline
on #Online.emp_num = #Offline.emp_num
and #Online.day_date = #Offline.day_date
and #Offline.StartDateTime between #Online.StartDateTime and #Online.EndDateTime
and #Offline.EndDateTime between #Online.StartDateTime and #Online.EndDateTime
declare @HoleNumber as integer
select @HoleNumber = isnull(MAX(OfflineHoleNumber),0) from #OfflineHoles
--Punch the holes out of the online times
While @HoleNumber > 0
Begin
insert into #Online
select
-1 Rownum,
#Online.emp_num,
#Online.day_date,
#OfflineHoles.EndDateTime StartDateTime,
#Online.EndDateTime EndDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
update #Online
set #Online.EndDateTime = #OfflineHoles.StartDateTime
from #Online
join #OfflineHoles
on #Online.Rownum = #OfflineHoles.Rownum
where OfflineHoleNumber = @HoleNumber
set @HoleNumber=@HoleNumber-1
end
--Output total hours
select emp_num, day_date,
SUM(datediff(second,StartDateTime, EndDateTime)) / 3600.0 TotalHr,
SUM(datediff(second,StartDateTime, EndDateTime)) / 60.0 TotalMin
from #Online
group by emp_num, day_date
order by 1, 2
--see how it split up the online intervals
select emp_num, day_date, StartDateTime, EndDateTime
from #Online
order by 1, 2, 3, 4
输出为：
emp_num day_date TotalHr TotalMin
----------- ----------------------- --------------------------------------- ---------------------------------------
547 2015-04-01 00:00:00.000 4.100000 246.000000
547 2015-04-02 00:00:00.000 0.816666 49.000000
548 2015-04-01 00:00:00.000 0.750000 45.000000
(3 row(s) affected)
emp_num day_date StartDateTime EndDateTime
----------- ----------------------- ----------------------- -----------------------
547 2015-04-01 00:00:00.000 2015-04-01 17:24:00.000 2015-04-01 21:30:00.000
547 2015-04-02 00:00:00.000 2015-04-02 13:11:00.000 2015-04-02 14:00:00.000
548 2015-04-01 00:00:00.000 2015-04-01 12:30:00.000 2015-04-01 13:15:00.000
(3 row(s) affected)
我留下了我的另一个答案，因为它更通用，以防其他人想抢走它。我看到你给这个问题加了赏金。让我知道我的回答中是否有某些具体内容不能让您满意，我会尽力帮助您。我用这种方法处理了数千个间隔，它 returns 只需几秒钟。
这里是 SQLFiddle 完整的查询。
我将展示如何构建一个查询，每个 emp_num, day_date 分钟数 returns。如果事实证明特定 emp_num, day_date 没有分钟剩余，那么结果将 没有 与 0 的行，根本没有这样的行.
总体思路
我会用一个table of numbers. We'll need only 24*60=1440 numbers, but it is a good idea to have such table in your database for other reports. I personally have it with 100,000 rows. Here is a very good article比较不同的方法来生成这样的table。
对于每个间隔，我将使用 table 的数字生成一组行 - 间隔中的每一分钟一行。我假设间隔是 [start; end)，即开始分钟包括在内，结束分钟不包括在内。例如，从 07:00 到 08:00 的间隔是 60 分钟，而不是 61.
生成 table 个数字
DECLARE @Numbers TABLE (N int);
INSERT INTO @Numbers(N)
SELECT TOP(24*60)
ROW_NUMBER() OVER(ORDER BY S.object_id) - 1 AS N
FROM
sys.all_objects AS S
ORDER BY N
;
对于此任务，最好使用从 0 开始的数字。通常您会将其作为永久 table，主键位于 N。
样本数据
DECLARE @Missions TABLE (emp_num int, day_date datetime, mission_in datetime, mission_out datetime);
DECLARE @Periods TABLE (emp_num int, day_date datetime, work_st datetime, work_end datetime, check_in datetime, check_out datetime, day_state char(1));
INSERT INTO @Missions (emp_num, day_date, mission_in, mission_out) VALUES
(547, '2015-04-01', '2015-04-01 15:00:00', '2015-04-01 21:30:00'),
(547, '2015-04-02', '2015-04-02 08:00:00', '2015-04-02 14:00:00');
INSERT INTO @Periods (emp_num, day_date, work_st, work_end, check_in, check_out, day_state) VALUES
(547, '2015-04-01', '2015-04-01 08:00:00', '2015-04-01 16:00:00', '2015-04-01 07:45:00', '2015-04-01 12:10:00', 'W'),
(547, '2015-04-01', '2015-04-01 08:00:00', '2015-04-01 16:00:00', '2015-04-01 12:45:00', '2015-04-01 17:24:00', 'W'),
(547, '2015-04-02', '2015-04-02 00:00:00', '2015-04-02 00:00:00', '2015-04-02 07:11:00', '2015-04-02 13:11:00', 'E');
我的解决方案不会使用 day_state 列。我希望您对 work_st 和 work_end 都有 00:00:00。解决方案要求同一行中的日期组件相同，并且 day_date 没有时间组件。
如果我为此任务设计架构，我将有三个 table 而不是两个：Missions、WorkPeriods 和 CheckPeriods。我会将您的 table Periods 分成两部分，以避免在多行中重复 work_st 和 work_end。但是这个解决方案将处理您当前的架构，并且它实际上会即时生成第三个 table。实际上，这意味着性能可能会有所提高。
任务分钟数
WITH
CTE_MissionMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
@Missions AS M
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, M.day_date, M.mission_in) AND
N.N < DATEDIFF(minute, M.day_date, M.mission_out)
)
@Missions 中的每个原始行变成一组行，间隔 (mission_in, mission_out) 的每一分钟一个。
工作时间
,CTE_WorkPeriods
AS
(
SELECT P.emp_num, P.day_date, P.work_st, P.work_end
FROM @Periods AS P
GROUP BY P.emp_num, P.day_date, P.work_st, P.work_end
)
生成第三个助手 table - 每个 emp_num, day_date, work_st, work_end 一行 - (work_st, work_end) 的所有间隔。
工作和检查分钟数
,CTE_WorkMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
CTE_WorkPeriods
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, CTE_WorkPeriods.day_date, CTE_WorkPeriods.work_st) AND
N.N < DATEDIFF(minute, CTE_WorkPeriods.day_date, CTE_WorkPeriods.work_end)
)
,CTE_CheckMinutes
AS
(
SELECT emp_num, day_date, N.N
FROM
@Periods AS P
CROSS JOIN @Numbers AS N
WHERE
N.N >= DATEDIFF(minute, P.day_date, P.check_in) AND
N.N < DATEDIFF(minute, P.day_date, P.check_out)
)
与 Missions 完全相同。
联盟"secondary intervals"
,CTE_UnionPeriodMinutes
AS
(
SELECT emp_num, day_date, N
FROM CTE_WorkMinutes
UNION ALL -- can be not ALL here, but ALL is usually faster
SELECT emp_num, day_date, N
FROM CTE_CheckMinutes
)
从主要间隔中减去次要间隔
,CTE_FinalMinutes
AS
(
SELECT emp_num, day_date, N
FROM CTE_MissionMinutes
EXCEPT
SELECT emp_num, day_date, N
FROM CTE_UnionPeriodMinutes
)
总结分钟数
SELECT
emp_num
,day_date
,COUNT(*) AS FinalMinutes
FROM CTE_FinalMinutes
GROUP BY emp_num, day_date
ORDER BY emp_num, day_date;
要进行最终查询，只需将所有 CTE 放在一起即可。
结果集
emp_num day_date FinalMinutes
547 2015-04-01 00:00:00.000 246
547 2015-04-02 00:00:00.000 49
There are 246 minutes between 17:24 and 21:30.
There are 49 minutes between 13:11 and 14:00.
这里是 SQLFiddle 完整的查询。
显示导致此 SUM 分钟的实际间隔相当容易，但您说您只需要 SUM.
我的解决方案与 Vladimir Baranov 非常相似。
Link 到 .NetFiddle
总体思路
我的算法基于 interval tree 的修改。假设最小时间单位为1分钟（易于修改）。
每个树节点处于 3 种状态之一：未访问、已访问和已使用。该算法基于递归 Search 函数，可通过以下步骤描述：
- 如果节点已使用或搜索区间为空则return空区间。
- 如果节点未访问且节点间隔等于搜索间隔，则将当前节点标记为已使用和return节点间隔。
- 将节点标记为已访问，拆分搜索间隔和 return 左右子节点 Search 的总和。
解决步骤
- 计算最大区间。
- 添加到树 "secondary intervals"。
- 添加到树 "main interval"。
计算间隔总和。
请注意 我假设间隔是 [start; end]，即两个区间都包含在内，容易改变。
要求
假设
n - "secondary intervals"
的数量米 - 基本单位的最大时间
构造需要 O(2n) 存储 space 并在 O(n log n + m) 时间内工作。
这是我的代码
public class Interval
{
public int Start { get; set; }
public int End { get; set; }
};
enum Node
{
Unvisited = 0,
Visited = 1,
Used = 2
};
Node[] tree;
public void Calculate()
{
var secondryIntervalsAsDates = new List<Tuple<DateTime,DateTime>> { new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 0, 0), new DateTime(2015, 03, 15, 5, 0, 0))};
var mainInvtervalAsDate = new Tuple<DateTime, DateTime>(new DateTime(2015, 03, 15, 3, 0, 0), new DateTime(2015, 03, 15, 7, 0, 0));
// calculate biggest interval
var startDate = secondryIntervalsAsDates.Union( new List<Tuple<DateTime,DateTime>>{mainInvtervalAsDate}).Min(s => s.Item1).AddMinutes(-1);
var endDate = secondryIntervalsAsDates.Union(new List<Tuple<DateTime, DateTime>> { mainInvtervalAsDate }).Max(s => s.Item2);
var mainInvterval = new Interval { Start = (int)(mainInvtervalAsDate.Item1 - startDate).TotalMinutes, End = (int)(mainInvtervalAsDate.Item2 - startDate).TotalMinutes };
var wholeInterval = new Interval { Start = 1, End = (int)(endDate - startDate).TotalMinutes};
//convert intervals to minutes
var secondaryIntervals = secondryIntervalsAsDates.Select(s => new Interval { Start = (int)(s.Item1 - startDate).TotalMinutes, End = (int)(s.Item2 - startDate).TotalMinutes}).ToList();
tree = new Node[wholeInterval.End * 2 + 1];
//insert secondary intervals
secondaryIntervals.ForEach(s => Search(wholeInterval, s, 1));
//insert main interval
var result = Search(wholeInterval, mainInvterval, 1);
//calculate result
var minutes = result.Sum(r => r.End - r.Start) + result.Count();
}
public IEnumerable<Interval> Search(Interval current, Interval searching, int index)
{
if (tree[index] == Node.Used || searching.End < searching.Start)
{
return new List<Interval>();
}
if (tree[index] == Node.Unvisited && current.Start == searching.Start && current.End == searching.End)
{
tree[index] = Node.Used;
return new List<Interval> { current };
}
tree[index] = Node.Visited;
return Search(new Interval { Start = current.Start, End = current.Start + (current.End - current.Start) / 2 },
new Interval { Start = searching.Start, End = Math.Min(searching.End, current.Start + (current.End - current.Start) / 2) }, index * 2).Union(
Search(new Interval { Start = current.Start + (current.End - current.Start) / 2 + 1 , End = current.End},
new Interval { Start = Math.Max(searching.Start, current.Start + (current.End - current.Start) / 2 + 1), End = searching.End }, index * 2 + 1));
}
我找到了可能是最简单的解决方案。
- 按开始日期排序 "Secondary intervals"。
- 寻找 "secondary intervals" 中的空白（简单迭代）
与"main interval"比较差距。
//declare intervals var secondryIntervals = new List<Tuple<DateTime, DateTime>> { new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 0, 0), new DateTime(2015, 03, 15, 5, 0, 0)), new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 10, 0), new DateTime(2015, 03, 15, 4, 40, 0)), new Tuple<DateTime, DateTime>( new DateTime(2015, 03, 15, 4, 40, 0), new DateTime(2015, 03, 15, 5, 20, 0))}; var mainInterval = new Tuple<DateTime, DateTime>(new DateTime(2015, 03, 15, 3, 0, 0), new DateTime(2015, 03, 15, 7, 0, 0)); // add two empty intervals before and after main interval secondryIntervals.Add(new Tuple<DateTime, DateTime>(mainInterval.Item1.AddMinutes(-1), mainInterval.Item1.AddMinutes(-1))); secondryIntervals.Add(new Tuple<DateTime, DateTime>(mainInterval.Item2.AddMinutes(1), mainInterval.Item2.AddMinutes(1))); secondryIntervals = secondryIntervals.OrderBy(s => s.Item1).ToList(); // endDate will rember 'biggest' end date var endDate = secondryIntervals.First().Item1; var result = secondryIntervals.Select(s => { var temp = endDate; endDate = endDate < s.Item2 ? s.Item2 : endDate; if (s.Item1 > temp) { return new Tuple<DateTime, DateTime>(temp < mainInterval.Item1 ? mainInterval.Item1 : temp, mainInterval.Item2 < s.Item1 ? mainInterval.Item2 : s.Item1); } return null; }) // remove empty records .Where(s => s != null && s.Item2 > s.Item1).ToList(); var minutes = result.Sum(s => (s.Item2 - s.Item1).TotalMinutes);
该算法需要 O(n log n) 时间（用于排序）而无需额外的存储和假设。