c# - raiz - ¿Cómo hacer cálculos en intervalos de tiempo?
multiplicaciones en numbers (5)
Tengo un problema, lo resuelvo, pero he escrito un largo procedimiento y no puedo estar seguro de que cubra todos los casos posibles.
El problema:
Si tengo un intervalo de tiempo principal (de From A to B ) y tiempos de intervalo secundarios (muchos o no)
(`From X to Y AND From X` to Y` AND X`` to Y`` AND ....`)
Quiero sumar todas las partes de Mi intervalo de tiempo principal (AB) fuera de los intervalos secundarios en minutos en forma eficiente y con el menor número de condiciones (procedimiento del servidor SQL y método C #).
Por ejemplo: si mi intervalo principal es de 02:00 to 10:30 y diga un intervalo secundario de 04:00 to 08:00
Ahora quiero este resultado: ((04:00 - 02:00) + (10:30 -08:00))* 60
Ejemplo con gráfica:
En el primer caso el resultado será:
((X-A) + (B-Y)) * 60
y será más complicado cuando tenga muchos periodos secundarios.
NOTA:
Puede ser que la superposición entre los intervalos secundarios ocurra solo cuando tengo que comparar el período principal [A, B] con la UNIÓN de a lo sumo dos conjuntos paralelos de intervalos secundarios . El primer conjunto debe contener solo un intervalo secundario y el segundo el conjunto contiene (muchos o no) intervalos secundarios. Por ejemplo, en el gráfico que compara [A,B] con (conjuntos de 2,5 ), el primer conjunto (2) consta de un intervalo secundario y el segundo conjunto (5) consta de Tres intervalos secundarios. y este es el peor de los casos, necesito manejarlo.
Por ejemplo :
SI mi intervalo principal es [15:00,19:40] y tengo dos conjuntos de intervalos secundarios. De acuerdo con mi regla, al menos uno de estos conjuntos debe consistir en un intervalo secundario. digamos que el primer conjunto es [11:00 ,16:00] y el segundo conjunto consiste en, por ejemplo, dos intervalos secundarios [10:00,15:00],[16:30,17:45] Ahora quiero el resultado (16:30 -16:00) +(19:40 -17:45)
Según los comentarios:
Mi mesa es así:
La primera tabla contiene períodos secundarios, como máximo dos conjuntos de períodos secundarios en la misma fecha para un empleado específico. el primer conjunto contiene solo un período secundario en el día laboral (W) [work_st,work_end] , y este conjunto estará vacío si el día es fin de semana [E] y, en este caso, no se superponen entre los períodos secundarios. y el segundo conjunto puede contener muchos períodos secundarios en la misma fecha [check_in,check_out] , porque el empleado puede check_in_out muchas veces en el mismo día.
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
La segunda tabla contiene el período principal [A,B] y es un período para este empleado en ese día (un registro)
emp_num day_date mission_in mission_out
547 2015-4-1 15:00 21:30
547 2015-4-2 8:00 14:00
En el ejemplo anterior, si tengo un procedimiento o método según sea necesario, este procedimiento debería tomar dos parámetros:
- La fecha
- El emp_num
en el ejemplo anterior debería ser así (''2015-4-1'' ,547)
Según mi explicación:
El período principal (período de la misión)
[A,B]de la segunda tabla: debe ser solo un período en esta fecha para ese empleado[15:00,21:30]El período secundario para la fecha aprobada
(''2015-4-1'')para ese empleado fue de dos grupos de períodos secundarios (el peor de los casos) de la primera tablaEl primer conjunto debe contener solo un período secundario (o períodos cero)
[08:00,16:00]el segundo conjunto podría contener muchos períodos secundarios (o períodos cero)[07:45,12:10],[12:45,17:24]
La salida debe ser [17: 24,21: 30] convertida a minutos
Nota
all day_date,mission_in,mission_out,work_st,work_end,check_in,check_out son campos de datetime y datetime pero pongo la hora en el ejemplo de simplificación, quiero ignorar la parte de la fecha, excepto la day_date porque es la fecha en la que calculo más. al emp_num .
Aquí está SQLFiddle con consulta completa.
emp_num, day_date cómo construí una consulta que devuelve la cantidad de minutos para cada emp_num, day_date . Si resulta que no quedan minutos para un emp_num, day_date particular emp_num, day_date , el resultado no tendrá una fila con 0 , no habrá tal fila en absoluto.
Idea general
Usaré una tabla de números . Solo necesitaremos 24*60=1440 números, pero es una buena idea tener dicha tabla en su base de datos para otros informes. Yo personalmente lo tengo con 100,000 filas. Aquí hay un muy buen artículo que compara diferentes métodos para generar dicha tabla.
Para cada intervalo, generaré un conjunto de filas utilizando la tabla de números: una fila por cada minuto en el intervalo. Supongo que los intervalos son [start; end) [start; end) , es decir, el minuto de inicio es inclusivo, el minuto de finalización es exclusivo. Por ejemplo, el intervalo de 07:00 a 08:00 es de 60 minutos, no de 61 .
Generar una tabla de números.
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
;
Para esta tarea, es mejor tener números que comiencen desde 0. Normalmente lo tendría como una tabla permanente con clave principal en N
Data de muestra
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'');
Mi solución no utilizará la columna day_state . Espero que tenga 00:00:00 para work_st y work_end . La solución espera que el componente de fecha dentro de la misma fila sea el mismo y que day_date no tenga componente de tiempo.
Si diseñara el esquema para esta tarea, tendría tres tablas en lugar de dos: Missions , WorkPeriods y CheckPeriods . Dividiría los Periods su tabla en dos para evitar repetir work_st y work_end en varias filas. Pero esta solución se ocuparía de su esquema actual y generará esencialmente esta tercera tabla sobre la marcha. En la práctica significa que el rendimiento puede ser mejorado.
Minutos de misión
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)
)
Cada fila original de @Missions convierte en un conjunto de filas, una para cada minuto del intervalo (mission_in, mission_out) .
Periodos de trabajo
,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
)
Genere una tercera tabla auxiliar: una fila para cada emp_num, day_date, work_st, work_end - todos los intervalos para (work_st, work_end) .
Minutos de trabajo y control
,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)
)
Exactamente lo mismo que para Missions .
Unión "intervalos secundarios"
,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
)
Restar intervalos secundarios de primaria
,CTE_FinalMinutes
AS
(
SELECT emp_num, day_date, N
FROM CTE_MissionMinutes
EXCEPT
SELECT emp_num, day_date, N
FROM CTE_UnionPeriodMinutes
)
Suma la cantidad de minutos
SELECT
emp_num
,day_date
,COUNT(*) AS FinalMinutes
FROM CTE_FinalMinutes
GROUP BY emp_num, day_date
ORDER BY emp_num, day_date;
Para hacer la consulta final solo tiene que poner todos los CTE juntos.
Conjunto resultante
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.
Aquí está SQLFiddle con consulta completa.
Es bastante fácil mostrar los intervalos reales que llevan a esta SUM de minutos, pero usted dijo que solo necesita la SUM .
Descubrí probablemente la solución más simple.
- Ordenar "Intervalos secundarios" por fecha de inicio.
- Busque espacios en "intervalos secundarios" (iteración simple)
Comparar espacios con "intervalo principal".
//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);
El algoritmo requiere tiempo O (n log n) (para clasificar) sin almacenamiento y suposiciones adicionales.
He actualizado mi respuesta con su ejemplo de datos y estoy agregando otro ejemplo para un empleado 248 que usa los casos 2 y 5 de su gráfica.
--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
La salida es:
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)
Dejé mi otra respuesta publicada porque es más genérica en caso de que alguien más quiera engancharla. Veo que has añadido una recompensa a esta pregunta. Avísame si hay algo específico en mi respuesta que no te satisface e intentaré ayudarte. Procesé miles de intervalos con este método y regresa en solo unos segundos.
Mi solución es bastante similar a Vladimir Baranov.
Enlace a .NetFiddle
Idea general
Mi algoritmo se basa en una modificación del árbol de intervalos . Se supone que la unidad de tiempo más pequeña es de 1 minuto (fácil de modificar).
Cada nodo de árbol está en 1 de 3 estados: no visitado, visitado y utilizado. El algoritmo se basa en la función de búsqueda recursiva que se puede describir mediante los siguientes pasos:
- Si se utiliza el nodo o el intervalo de búsqueda está vacío, devuelva el intervalo vacío.
- Si el nodo no está visitado y el intervalo de nodos es igual al intervalo de búsqueda, marque el nodo actual como utilizado y devuelva el intervalo de nodo.
- Marque el nodo como visitado , divida el intervalo de búsqueda y devuelva la suma de Búsqueda de elementos secundarios izquierdo y derecho.
Solución en pasos
- Calcula el mayor intervalo.
- Añadir al árbol "intervalos secundarios".
- Añadir al árbol "intervalo principal".
Calcular suma de intervalos.
Tenga en cuenta que supongo que los intervalos son [inicio; fin], es decir, ambos intervalos son inclusivos, lo que es fácil de cambiar.
Requerimientos
Asumiendo
n - número de "intervalos secundarios"
m - tiempo máximo en unidad base
La construcción requiere O (2n) espacio de almacenamiento y trabajo en tiempo O (n log n + m).
Aquí está mi código
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));
}
Tuve que resolver este problema para digerir algunos datos de programación. Esto permite múltiples tiempos en línea, pero supone que no se superponen.
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