Lógica eficiente para obtener valores distintos de un rango de valores en C# 2.0

Question

Tengo una lista de rangos. Cada rango tiene un valor desde y hacia, lo que significa que el valor puede estar entre ese rango. Por ejemplo, si el rango es (1,4)., Los valores pueden ser 1,2,3 y 4. Ahora, necesito encontrar los valores distintos en una lista dada de rango. A continuación se muestra el código de muestra.

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<Range> values = new List<Range>(); 
     values.Add(new Range(1, 2)); 
     values.Add(new Range(1, 3)); 
     values.Add(new Range(1, 4)); 
     values.Add(new Range(3, 5)); 
     values.Add(new Range(7, 10)); 
     values.Add(new Range(7, 8)); 

     // Expected Output from the range of values 
     //1,2,3,4,5,7,8,9,10 
    } 
} 
class Range 
{ 
    public Range(int _form, int _to) 
    { 
     from = _from; 
     to = _to; 
    } 
    private int from; 

    public int From 
    { 
     get { return from; } 
     set { from = value; } 
    } 

    private int to; 

    public int To 
    { 
     get { return to; } 
     set { to = value; } 
    } 

} 

Puedo recorrer cada rango y encontrar los distintos valores. pero si alguien puede dar un enfoque eficaz, sería útil.

Answer 1

• Para un pequeño número de intervalos, el enfoque directo debería ser el truco.
• Si la mayoría de los intervalos se pliegan entre sí, se puede realizar una etapa preliminar de su fusión para reducir el número de pruebas
• Si el número de intervalos disjuntos es alta, construir un Interval Tree. Aquí hay un link a un artículo con código de ejemplo en Java.

Answer 2

Por favor, considere la siguiente solución (no voy a escribir el código completo, única vía general):

• para cada ajustar las variables MINVAL y Maxval entrantes Rango - para contener el valor mínimo en todos los rangos, y valor máximo en todos los rangos respectivamente
• construcción de dos colecciones de rangos de entrada, dejó un nombre sea Begins y el otro Ends
• después de todos los rangos se recogen tanto las colecciones tipo: Begins debe ordenarse según t O from valor y Ends deben ser ordenados según la to valor
• inicializar depth variable de contador a 0
• inicializar BeginPointer y EndPointer al primer elemento de las respectivas colecciones
• ahora la parte crucial: iterar desde MinVal a MaxVal, si la corriente el valor indica el comienzo de la recopilación (el número en el actual BeginPointer es igual al valor de iteración) -> aumenta depth en 1 y mueve BeginPointer hacia adelante (repite para "inicios" consecutivos)
• Si depth es mayor que 0 - valor actual iteración> impresión como estamos dentro de un rango
• si el valor actual indica que termina de colección -> disminuir depth por 1 (repita para "finales" consecutivos)

Esta voluntad hacer para incluso un gran rango de valores. Si el valor máximo es relativamente bajo (es decir, 1000, como OP indicado en los comentarios, consulte mi otra respuesta).

Answer 3

Si el rango de _from y _to es pequeño (1000 como se indica) puede usar una matriz [1000] de booleanos. Para cada rango entrante, establezca los elementos de matriz correspondientes en verdadero. Es decir. para Rango (3,6), establezca los elementos de matriz 3, 4, 5 y 6 en verdadero. Ahora itere sobre la matriz e imprima todos los índices que sean verdaderos. Debe ser lo suficientemente eficiente para pequeños rangos.