algoritmo reto: rango de fechas fusión

Question

estoy frente a un problema interesante:

• Tengo varios intervalos de tiempo que pueden solaparse
• cada uno de ellos tiene un nombre

¿Es posible "des-traslapar" estos rangos? Es decir, para generar:

• un nuevo conjunto de rangos donde no se superpone a los otros
• cada una de esta nueva gama cuenta con una lista de nombres correspondientes

Tal vez pueda hacer esto un poco más gráfico. Esto es lo que tengo en primer lugar:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

Esto es lo que me gustaría obtener:

|------|---------|-------|-----|-----| 
     a  a,c  a,b,c a,b b 

he encontrado una solución que tipo de obras, pero que no es elegante:

1. Transformo cada rango (de, a) en una lista de días (d1, d2, d3, etc.)
2. Nombres de grupos por día
3. Agrego grupos que contienen los mismos nombres para recrear rangos

¿Puede pensar en una solución mejor? Estoy trabajando con C#, pero cualquier idea independiente del lenguaje sería muy apreciada. ¡Gracias!

Answer 1

Me

1. Mantener una lista desordenada de "abierta" rangos
2. de inicio desde el día 1, y añadir el primer rango de la lista de rangos abierta.
3. Mueva hasta el siguiente límite de rango (ya sea inicio o cierre). Crea tu primer rango de "salida": comenzando desde el día 1 hasta ese día. En él están los artículos en su lista de rangos abiertos.
4. Si el rango encontrado ya está en la lista de rangos abiertos, elimínelo. De lo contrario, agrégalo.
5. Repita los pasos 3 y 4, moviéndose a lo largo de la línea.

Definitivamente hice un mal trabajo al explicarlo. Pronto escribiré un código para esto. Pero hasta entonces, esto es lo que sucedería en su solución:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

 
1. Start at day 1, add A to open ranges list, which now contains [A] 
2. Move to the start of C. First RESULT RANGE: A range from Day 1 to C's start, 
     with a value A. (what is in your open ranges list) 
3. Add C to the open ranges list, which now contains [A,C] 
4. Move to the start of B. Second RESULT RANGE: A range from C's start to B's 
     start, with a value A,C. (what is in your open ranges list) 
5. Add B to the open ranges list, which now contains [A,C,B] 
6. Move to the end of C. Third RESULT RANGE: A range from B's start to C's end, 
     with a value of A,C,B. 
7. Remove C from the open ranges list, which now contains [A,B] 
8. Move to the end of A. Fourth RESULT RANGE: A range from C's end to A's end, 
     with a value of A,B 
9. Remove A from the open ranges list, which now contains [B] 
10. Move to the end of A. Fourth RESULT RANGE: A range from A's end to B's end, 
     with a value of B 

RESULT RANGES 
1. from Day 1 to C's start: A 
2. from C's start to B's start: A,C 
3. from B's start to C's end: A,C,B 
4. from C's end to A's end: A,B 
5. from A's end to B's end: B 

---

Método alternativo

Usted puede hacer esto:

1. Mantener una lista ordenada de "rangos de salida ". Esto hace que sea fácil probar si un punto está dentro de un rango, y también qué rangos se siguen uno al otro.
2. Tome un rango de sus rangos de entrada.
3. Compruebe si está completamente antes o completamente después de todos los rangos de salida, y manipúlelo según corresponda. Omita los siguientes pasos y vuelva al paso 2, de ser así.
4. Compare su punto de inicio con los rangos de salida
5. Si es antes de cualquier otro rango de salida, agregue un nuevo rango de salida desde su inicio hasta el inicio del primer rango de salida.
6. Si esto se encuentra entre un rango de salida ya existente, divida ese rango de salida en ese punto. La primera parte contendría los mismos "padres", y la segunda parte tendría los mismos padres + el nuevo rango de entrada.
7. Ahora, compare su punto final con los rangos de salida.
8. Si está después de cualquier otro rango de salida, agregue un nuevo rango de salida desde el final del último rango de salida hasta el final.
9. Si esto se encuentra entre un rango de salida ya existente, divida ese rango de salida en ese punto. La segunda parte contendría los mismos "padres", y la primera parte tendría los mismos padres + el nuevo rango de entrada
10. Agregue el rango de entrada actual como una parte a todos los rangos entre los dos rangos "procesados" en los pasos 6 y 9, si hay alguno.
11. Repita 2-6 para todos los rangos de entrada.

Éstos son los primeros pasos, utilizando los datos de muestra + otro rango D: (rangos "procesados" indicado por **double stars**)

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 
d  |------------------------| 

 

1. 
    Process A 
    Output ranges: |--------------A---------------| 
2. 
    Process B 
    - Start of B is in **A**; split A in two: 
        |-------A-------|------AB------| 
    - End of B is after any output range range; 
     creating new output range at end 
        |-------A-------|------AB------|---B---| 
    - Nothing was/is in between **A** and (nothing) 
3. 
    Process C 
    - Start of C is in **A**; split A in two: 
        |---A----|--AC--|------AB------|---B---| 
    - End of C is in **AB**; split AB in two: 
        |---A----|--AC--|--ABC--|--AB--|---B---| 
    - There were/are no ranges between **A** and **AB** 

4. 
    Process D 
    - Start of D is in **A**; split A in two: 
        |-A-|-AD-|--AC--|--ABC--|--AB--|---B---| 
    - End of D is in **AB**; split AB in two: 
        |-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---| 
    - Ranges AC and ABC were/are in between **A** and **AB** 
        |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Final output:  |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Answer 2

Es posible que desee tener vistazo a Interval Trees .

Answer 3

Usted podría:

1. ordenar la lista de todas las fechas (la combinación de la fechas desde y hasta)
2. luego corriendo a lo largo de esta lista, cada nuevo rango sería de una fecha a la próxima principio o al final fecha que es diferente de la anterior.

Para nombrar los nuevos rangos, tiene sentido tener la lista de nombres de rango originales que contiene el nuevo rango actual, y cada vez que llegue a una fecha de finalización, elimine el nombre antiguo de la lista, y cada tiem golpeas una fecha de inicio, agrega su nombre a la lista.

Answer 4

hacer esto:

crear una clase Event.

class DateEvent : IComparable<DateEvent> 
{ 
    public Date Date; 
    public int DateRangeId; 
    public bool IsBegin; // is this the start of a range? 

    public int CompareTo(DateEvent other) 
    { 
     if (Date < other.Date) return -1; 
     if (Date > other.Date) return +1; 
     if (IsBegin && !other.IsBegin) return -1; 
     if (!IsBegin && other.IsBegin) return +1; 
     return 0; 
    } 
} 

definir un List<DateEvent> events;

Agregar inicio y final de cada rango en la lista:

for (int i = 0; i < dateRanges.Length; ++i) 
{ 
    DateRange r = dateRanges[i]; 
    events.Add(new DateEvent(r.BeginDate, i, true)); 
    events.Add(new DateEvent(r.EndDate, i, false)); 
} 

Ordenar los acontecimientos.

events.Sort(); 

Ahora configura una clase de salida:

class OutputDateRange 
{ 
    public Date BeginDate; 
    public Date EndDate; 
    public List<string> Names; 
} 

Por último, atraviesan los eventos, manteniendo que oscila están presentes:

List<int> activeRanges; 
List<OutputDateRange> output; 
Date current = events[0].Date; 
int i = 0; 

while (i < events.Length;) 
{ 
    OutputDateRange out = new OutputDateRange(); 
    out.BeginDate = current; 

    // Find ending date for this sub-range. 
    while (i < events.Length && events[i].Date == current) 
    { 
     out.EndDate = events[i].Date; 
     if (events[i].IsBegin) 
      activeRanges.Add(events[i].DateRangeId); 
     else 
      activeRanges.Remove(events[i].DateRangeId); 
     ++i; 
    } 

    if (i < events.Length) 
     current = events[i].Date; 

    foreach (int j in activeRanges) 
     out.Names.Add(dateRanges[j].Name); 

    output.Add(out); 
} 

Que debe hacer el truco. Tenga en cuenta que no he hecho los constructores, y el código es un poco feo, pero espero que transmita la idea general.

Answer 5

Tengo un código que hace esto. Se basa en el conjunto de entrada ordenado por from y luego to (es decir, si era SQL, sería ORDER BY from_value, to_value), pero después de eso es bastante óptimo.

Mi implementación básicamente hace lo que describe @Justin L. 's answer, así que si solo quieres una descripción textual, mira su respuesta para el algoritmo.

El código está aquí: LVK.DataStructures, y los archivos que desea mirar son:

• Range.cs
• RangeExtensions.cs, en particular el método de la rebanada en line 206 y en adelante.

Para usarlo:

List<Range<DateTime>> ranges = ... 
var slices = ranges.Slice(); 

esto le dará una nueva gama para cada sector, y para cada uno de tales rango que tendría una propiedad .Data que contiene referencias de nuevo a los rangos de contribuyentes.

es decir. para su ejemplo original, obtendría exactamente lo que desea, rangos individuales, con los rangos contribuyentes a, b, c, etc. en la propiedad .Data.

Las clases pueden usar otras partes de la biblioteca de mi clase, que está allí. Si decide usarlo, simplemente copie las porciones que desea usar.

Si solo está interesado en la implementación, se puede encontrar en el archivo RangeExtensions.cs, line 447 y en adelante, método InternalSlice.

Answer 6

1. Tengo una lista en primer lugar, no sé su longitud, pero tengo 3 caracteres
2. cheque por una ranura, si A no? agregar 'A', si B hay? agregar 'B', si c hay? añadir 'C'
3. ir a otra ranura, ciclo como # 2
4. final cuando nada añadido a otra nueva ranura
5. me dio la lista
6. aplanar la lista