我有一个问题,我解决了它,但我写了一个很长的过程,我不能确定它涵盖了所有可能的情况。
问题是:
如果我有main interval time (From A to B
)和辅助interval time(多或否)
(`From X to Y AND From X` to Y` AND X`` to Y`` AND ....`)
我想求和我的主间隔时间(AB)的所有部分,out of次间隔in 分钟, in efficient和最少数量的条件(SQL server过程和C#方法)?
例如:如果我的主要间隔来自02:00 to 10:30
,而次要间隔来自04:00 to 08:00
现在我想要这个结果:((04:00 - 02:00) + (10:30 -08:00))* 60
图的例子:
在第一种情况下,结果将是:
((X-A) + (B-Y)) * 60
而且当我有很多第二阶段的时候,它会变得更复杂。
注意:
可能仅当我必须将主周期A、B与最多两组平行的次要间隔的并集并集进行比较时,才会发生次要间隔之间的重叠。第一组必须仅包含一个次要间隔,而第二组包含(许多或不包含)次要间隔的示例。在比较[A,B]
和( of 2,5
)的图中,第一组(2)
由一个次要间隔组成,第二组(5)
由三个次要间隔组成。这是最糟糕的情况,我需要处理。
例如:
如果我的主区间是[15:00,19:40]
,并且根据我的规则,我有两组次要区间.according,那么这些集合中至少有一个应该由一个次要区间组成。假设第一个集合是[11:00 ,16:00]
,第二个集合由两个辅助区间[10:00,15:00],[16:30,17:45]
组成,现在我想要结果(16:30 -16:00) +(19:40 -17:45)
根据评论:
我的表是这样的:
第一个表包含辅助期间,对于特定员工,同一日期最多有两组辅助期间。第一个集合在work (W)
[work_st,work_end]
中只包含一个辅助期间,如果日期是weekend [E]
,则此集合将为空,并且在本例中辅助期间之间没有重叠。第二个集合可以包含同一日期内的许多次要期间,因为员工可以在同一天内多次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
第二个表包含主period[A,B]
,它是该员工当天的一个period (一个记录)
emp_num day_date mission_in mission_out
547 2015-4-1 15:00 21:30
547 2015-4-2 8:00 14:00
在前面的例子中,如果我有一个需要的过程或方法,这个过程应该有两个参数:
在前面的示例中,它应该是这样的('2015-4-1' ,547)
根据我的解释:
第二个表中的
[A,B]
:对于该员工,此日期中只能有一个期间该员工的通过日期('2015-4-1')
的辅助期间是第一个表中的两组辅助期间(最坏的情况)
第一个集合应该只包含一个次要期间(或零个期间) [08:00,16:00]
第二个集合可以包含许多次要期间(或零个期间)
[12:45,17:24]
,[07:45,12:10]
输出应为17:24,21:30转换为分钟
备注
所有的day_date,mission_in,mission_out,work_st,work_end,check_in,check_out
都是datetime
字段,但为了简化起见,我在示例中只放了时间,我想忽略除day_date
之外的日期部分,因为除了emp_num
之外,它是我计算的日期。
发布于 2015-04-15 08:24:45
我已经使用您的数据示例更新了我的答案,并为使用您的图表中的案例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)
我把我的另一个答案留在了网上,因为它更通用,以防其他人想要抓住它。我看到你在这个问题上加了一笔赏金。如果我的答案有什么不能让你满意的地方,请告诉我,我会尽力帮助你。我用这个方法处理了数千个时间间隔,它在几秒钟内就返回了。
发布于 2015-04-10 06:56:19
我不得不解决这个问题来消化一些日程安排数据。这允许多个在线时间,但假设它们不重叠。
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
发布于 2015-04-17 20:25:07
我的解决方案与弗拉基米尔·巴拉诺夫非常相似。
链接到.NetFiddle
通用idea
我的算法是基于对interval tree的修改。它假设最小的时间单位是1分钟(易于修改)。
每个树节点处于三种状态中的一种:未访问、已访问和已使用。该算法基于递归搜索函数,可以通过以下步骤来描述:
步骤中的解决方案
计算最大的interval.
请注意,我假设间隔是start;end,即两个间隔都包含在内,这很容易更改。
Requirements
假设
N-“二级间隔”的数量
M-以基本单位表示的最大时间
构造所需存储空间为O(2n),工作时间为O(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));
}
https://stackoverflow.com/questions/29549117
复制相似问题