Encontrar intervalos elementales en intervalos superpuestos

Question

Me encontré con una buena pregunta mientras me preparaba para algunas entrevistas de programación.

Dado un conjunto de intervalos posiblemente superpuestos, necesita escribir una función para devolver todos los intervalos elementales entre ellos. Por ejemplo: si se te dan intervalos como la siguiente lista de pares: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, entonces necesitas para devolver lo siguiente:

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20 }}

Nota lo siguiente en la respuesta anterior:

• el intervalo {11,15} se omite en la respuesta, ya que es inexistente en la entrada.
• El intervalo {1,5} de la entrada se ha dividido en {1,3}, {3,5} en la respuesta debido al punto de inicio "3" definido en {3,10} en la entrada que corta el intervalo en dos intervalos elementales.

firma del método en Java:

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals) 

Una de las soluciones que imaginé era separar la entrada en conjuntos no entrecruzadas, y luego un O sencilla (NlogN) ordenar más de todos los números en cada el conjunto sin intersección arrojará la respuesta. ¿Hay una forma más eficiente de hacerlo?

Answer 1

Se podría romper este problema arriba en intervalos anidados en primer lugar, a continuación, tratar con cada anidación por separado. Por anidados, quiero decir intervalos que comparten al menos un punto.Para el ejemplo que diste:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}} 

hay dos agrupamientos:

{1,5}, {3,10}, {5,11} 

y

{15,18}, {16,20} 

En general, para determinar los anidamientos, puede ordenar los intervalos basados ​​en la izquierda punto final (como en su ejemplo), luego ejecute e inicie una nueva anidación cada vez que vea {x,y}, {x',y'} con y < x'.

Para anidar, los "intervalos elementales" están formados por la secuencia ordenada (sin repeticiones) de valores. En el ejemplo, los anidamientos dan

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11} 

y

(15,16,18,20) -> {15,16}, {16,18}, {18,20} 

lo tanto, el algoritmo general puede tener este aspecto:

• Ordenar los intervalos basados ​​en el extremo izquierdo
• Ejecutar a través intervalos hasta {x,y}, {x',y'} con y < x'
• Fr om comenzando a {x,y}, hacer lista ordenada de puntos finales (sin repeticiones), dicen a0,a1,...,ak
• Añadir intervalos elementales {ai,a(i+1)} para i = 0...k-1
• Retire intervalos de hasta {x,y} y continúe desde el paso 2

Answer 2

Un algoritmo simple sería simplemente leer toda la lista de números y crear un elemento para cada elemento en cada par.

Cada elemento almacenaría dos valores: el number, y si es el primer o el segundo número (de la entrada).

Esos pares entonces serían ordenados, en primer lugar por su interior number, y luego por su posición (second irían antes first)

Para imprimir la lista de intervalos, en que imprime cada número junto con la siguiente número, con las siguientes reglas:

• no se imprimiría números repetidos (así, por ejemplo, usted no imprimir 5,5)
• Si usted tiene un número exclusivo second, y luego un first número, no imprimiría ese intervalo elemental, ya que no hay valores dentro de ese rango.

Answer 3

Puede ordenar los puntos finales y luego iterar en orden. Para saber si está dentro o fuera, puede mantener el número de intervalos que cubren cada punto. El extremo izquierdo del intervalo contribuye 1, mientras que la derecha contribuye -1: (Nótese que uso TreeMap, la cual se ordena)

static class Pair<T, K> { 
    public Pair(T first, K second){ 
     this.first = first; 
     this.second = second; 
    } 

    public String toString(){ 
     return "(" + first + ", " + second + ")"; 
    } 

    T first; 
    K second; 
}  

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) { 
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>(); 
    for(Pair<Integer, Integer> interval : intervals){ 
     int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1; 
     overlaps.put(interval.first, value); 

     value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1; 
     overlaps.put(interval.second, value); 
    } 

    List<Pair<Integer, Integer>> retValue = new ArrayList<Pair<Integer,Integer>>(); 

    int overlap = 0; 
    boolean in = false; 
    int last = 0; 
    for(int point : overlaps.keySet()){ 
     if(in) 
      retValue.add(new Pair(last, point)); 

     overlap += overlaps.get(point); 
     last = point; 
     in = overlap > 0; 
    } 

    return retValue; 
}  

public static void main(String[] args) { 

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>(); 
    l.add(new Pair<Integer, Integer>(1,5)); 
    l.add(new Pair<Integer, Integer>(3,10)); 
    l.add(new Pair<Integer, Integer>(5,11)); 
    l.add(new Pair<Integer, Integer>(15,18)); 
    l.add(new Pair<Integer, Integer>(16,20)); 

    for(Object o : generateElementaryIntervals(l)){ 
     System.out.println(o.toString()); 
    } 

}