Pregunta Determinar si dos rangos de fechas se superponen


Dado dos intervalos de fechas, ¿cuál es la forma más simple o más eficiente de determinar si los dos intervalos de fechas se superponen?

Como ejemplo, supongamos que tenemos rangos indicados por las variables DateTime StartDate1 a EndDate1  y  StartDate2 a EndDate2.


984
2017-11-28 14:48


origen


Respuestas:


(StartA <= EndB) y (EndA> = StartB)

Prueba:
Deje que ConditionA signifique que DateRange A completamente después de DateRange B
_ |---- DateRange A ------| |---Date Range B -----| _
  (Verdadero si StartA > EndB)

Deje que ConditionB signifique que DateRange A esté completamente antes de DateRange B
|---- DateRange A -----| _ _ |---Date Range B ----|
 (Verdadero si EndA < StartB)

Entonces Superposición existe si Ni A ni B es verdadero -
 (Si un rango no está completamente después del otro,
   ni completamente antes que el otro,      entonces deben superponerse)

Ahora uno de Las leyes de De Morgan dice que:

Not (A Or B)  <=> Not A And Not B

Que se traduce a: (StartA <= EndB) and (EndA >= StartB)


NOTA: Esto incluye condiciones donde los bordes se superponen exactamente. Si desea excluir eso,
cambiar el >= operadores a >y <=  a < 


NOTA 2. Gracias a @Baodad, mira este blog, la superposición real es menor de:
  { endA-startA, endA - startB, endB-startA, endB - startB }

(StartA <= EndB) and (EndA >= StartB) (StartA <= EndB) and (StartB <= EndA)


NOTA 3. Gracias a @tomosius, una versión más corta dice:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
En realidad, se trata de un acceso directo sintáctico para una implementación más larga, que incluye comprobaciones adicionales para verificar que las fechas de inicio estén en o antes de las fechas de finalización. Derivando esto de arriba:

Si las fechas de inicio y finalización pueden estar fuera de servicio, es decir, si es posible que startA > endA o startB > endB, entonces también debe verificar que estén en orden, lo que significa que debe agregar dos reglas de validez adicionales:
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB) o:
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB) o,
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB)) o:
(Max(StartA, StartB) <= Min(EndA, EndB) 

Pero para implementar Min() y Max(), tienes que codificar, (usando C ternary para la concisión) ,:
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB) 


1869
2017-11-28 15:00



Creo que es suficiente decir que los dos rangos se superponen si:

(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)

320
2017-11-28 14:49



Este artículo Time Period Library para .NET describe la relación de dos períodos de tiempo por la enumeración PeriodRelation:

// ------------------------------------------------------------------------
public enum PeriodRelation
{
    After,
    StartTouching,
    StartInside,
    InsideStartTouching,
    EnclosingStartTouching,
    Enclosing,
    EnclosingEndTouching,
    ExactMatch,
    Inside,
    InsideEndTouching,
    EndInside,
    EndTouching,
    Before,
} // enum PeriodRelation

enter image description here


87
2018-04-08 22:42



Para razonar sobre las relaciones temporales (o cualquier otra relación de intervalos, llegar a eso), considere Allen's Interval Algebra. Describe las 13 relaciones posibles que dos intervalos pueden tener entre sí. Puede encontrar otras referencias: "Allen Interval" parece ser un término de búsqueda operativa. También puede encontrar información sobre estas operaciones en Snodgrass's Desarrollar aplicaciones orientadas al tiempo en SQL (PDF disponible en línea en la URL), y en Date, Darwen y Lorentzos Datos temporales y el modelo relacional (2002) o Tiempo y teoría relacional: bases de datos temporales en el modelo relacional y SQL (2014, efectivamente la segunda edición de TD & RM).


La respuesta corta (ish) es: dados dos intervalos de fechas A y B con componentes .start y .end y la restricción .start <= .end, luego dos intervalos se superponen si:

A.end >= B.start AND A.start <= B.end

Puedes sintonizar el uso de >= vs > y <= vs < para cumplir con sus requisitos para el grado de superposición.


ErikE comenta:

Solo puedes obtener 13 si cuentas cosas divertidas ... Puedo obtener "15 relaciones posibles que pueden tener dos intervalos" cuando me vuelvo loco. Con un conteo sensato, obtengo solo seis, y si descartas la preocupación de si A o B son los primeros, solo obtengo tres (no se cruzan, parcialmente se cruzan, uno totalmente dentro de otro). 15 va así: [antes: antes, inicio, dentro, fin, después], [inicio: inicio, dentro, fin, después], [dentro: dentro, fin, después], [fin: fin, después], [ después: después].

Creo que no puede contar las dos entradas 'antes: antes' y 'después: después'. Pude ver 7 entradas si comparas algunas relaciones con sus inversas (mira el diagrama en la URL de Wikipedia referenciada, tiene 7 entradas, 6 de las cuales tienen una inversa diferente, con iguales que no tienen una inversa distinta). Y si tres es sensato depende de sus requisitos.

----------------------|-------A-------|----------------------
    |----B1----|
           |----B2----|
               |----B3----|
               |----------B4----------|
               |----------------B5----------------|
                      |----B6----|
----------------------|-------A-------|----------------------
                      |------B7-------|
                      |----------B8-----------|
                         |----B9----|
                         |----B10-----|
                         |--------B11--------|
                                      |----B12----|
                                         |----B13----|
----------------------|-------A-------|----------------------

66
2017-11-30 06:54



Si también se debe calcular la superposición, puede usar la siguiente fórmula:

overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) { 
    ...
}

25
2017-09-06 02:07



Todas las soluciones que verifican una multitud de condiciones en función de dónde están los rangos entre sí pueden simplificarse enormemente mediante ¡solo asegúrate de que un rango específico comience antes! Asegúrate de que el primer rango comience antes (o al mismo tiempo) intercambiando los rangos si es necesario por adelantado.

Luego, puede detectar superposición si el otro rango de inicio es menor o igual que el primer rango final (si los rangos son inclusivos, que contiene los tiempos de inicio y fin) o menor que (si los rangos incluyen el inicio y no el final) .

Suponiendo que ambos extremos son inclusivos, solo hay cuatro posibilidades de las cuales una no se solapa:

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 overlap
                        |--->   range 2 no overlap

El punto final del rango 2 no entra en él. Entonces, en pseudo-código:

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    if r2.s > r1.e:
        return false
    return true

Esto podría simplificarse aún más en:

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    return r2.s <= r1.e

Si los rangos son inclusivos al principio y exclusivos al final, solo tiene que reemplazar > con >= en el segundo if declaración (para el primer segmento de código: en el segundo segmento de código, usarías < más bien que <=)

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 no overlap
                        |--->   range 2 no overlap

Limita enormemente el número de comprobaciones que tiene que hacer porque elimina la mitad del espacio problemático antes de tiempo, asegurando que el rango 1 nunca se inicie después del rango 2.


16
2017-08-06 02:39



Aquí hay otra solución usando JavaScript. Especialidades de mi solución:

  • Maneja valores nulos como infinito
  • Supone que el límite inferior es inclusivo y el límite superior exclusivo.
  • Viene con un montón de pruebas

Las pruebas se basan en enteros, pero dado que los objetos de fecha en JavaScript son comparables, también puedes incluir dos objetos de fecha. O podrías lanzar la marca de tiempo de milisegundos.

Código:

/**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
function intervalsOverlap(from1, to1, from2, to2) {
    return (to2 === null || from1 < to2) && (to1 === null || to1 > from2);
}

Pruebas:

describe('', function() {
    function generateTest(firstRange, secondRange, expected) {
        it(JSON.stringify(firstRange) + ' and ' + JSON.stringify(secondRange), function() {
            expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
        });
    }

    describe('no overlap (touching ends)', function() {
        generateTest([10,20], [20,30], false);
        generateTest([20,30], [10,20], false);

        generateTest([10,20], [20,null], false);
        generateTest([20,null], [10,20], false);

        generateTest([null,20], [20,30], false);
        generateTest([20,30], [null,20], false);
    });

    describe('do overlap (one end overlaps)', function() {
        generateTest([10,20], [19,30], true);
        generateTest([19,30], [10,20], true);

        generateTest([10,20], [null,30], true);
        generateTest([10,20], [19,null], true);
        generateTest([null,30], [10,20], true);
        generateTest([19,null], [10,20], true);
    });

    describe('do overlap (one range included in other range)', function() {
        generateTest([10,40], [20,30], true);
        generateTest([20,30], [10,40], true);

        generateTest([10,40], [null,null], true);
        generateTest([null,null], [10,40], true);
    });

    describe('do overlap (both ranges equal)', function() {
        generateTest([10,20], [10,20], true);

        generateTest([null,20], [null,20], true);
        generateTest([10,null], [10,null], true);
        generateTest([null,null], [null,null], true);
    });
});

Resultado cuando se ejecuta con karma & jazmín y PhantomJS:

PhantomJS 1.9.8 (Linux): ejecutado 20 de 20 SUCCESS (0.003 segs / 0.004 secs)


12
2018-03-13 13:19



Sé que esto ha sido etiquetado como independiente del lenguaje, pero para todos ustedes que implementan en Java: No reinventen la rueda y usen Joda Time.

http://joda-time.sourceforge.net/api-release/org/joda/time/base/AbstractInterval.html#overlaps(org.joda.time.ReadableInterval)


8
2017-10-13 15:10



yo lo haría

StartDate1.IsBetween(StartDate2, EndDate2) || EndDate1.IsBetween(StartDate2, EndDate2)

Dónde IsBetween es algo así como

    public static bool IsBetween(this DateTime value, DateTime left, DateTime right) {
        return (value > left && value < right) || (value < left && value > right);
    }

7
2017-11-28 14:51



La solución publicada aquí no funciona para todos los rangos superpuestos ...

---------------------- | ------- A ------- | ----------- -----------
    | ---- B1 ---- |
           | ---- B2 ---- |
               | ---- B3 ---- |
               | ---------- B4 ---------- |
               | ---------------- B5 ---------------- |
                      | ---- B6 ---- |
---------------------- | ------- A ------- | ----------- -----------
                      | ------ B7 ------- |
                      | ---------- B8 ----------- |
                         | ---- B9 ---- |
                         | ---- B10 ----- |
                         | -------- B11 -------- |
                                      | ---- B12 ---- |
                                         | ---- B13 ---- |
---------------------- | ------- A ------- | ----------- -----------

mi solución de trabajo fue:

AND (
  ('start_date' ENTRE STARTDATE Y ENDDATE) - abastece la fecha interna y final externa
  O
  ('end_date' ENTRE STARTDATE Y ENDDATE): abastece la fecha de inicio y la fecha de inicio externa
  O
  (STARTDATE ENTRE 'start_date' Y 'end_date') - solo se necesita uno para el rango externo donde las fechas están dentro.
)

5
2017-11-05 08:24