Unión de intervalos

Question

Tengo una clase que representa un intervalo. Esta clase tiene dos propiedades "inicio" y "final" de un tipo comparable. Ahora estoy buscando un algoritmo eficiente para tomar la unión de un conjunto de tales intervalos.

Gracias de antemano.

Answer 1

Ordene por uno de los términos (comience, por ejemplo), luego verifique las superposiciones con su vecino (derecho) a medida que avanza por la lista.

class tp(): 
    def __repr__(self): 
     return '(%d,%d)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(5,10),tp(7,8),tp(0,5)] 
s.sort(key=lambda self: self.start) 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 

Answer 2

Utilice el algoritmo sweep line. Básicamente, ordena todos los valores en una lista (mientras mantiene si es el principio o el final del intervalo junto con cada elemento). Esta operación es O (n log n). A continuación, realiza un bucle en una sola pasada a lo largo de los elementos ordenados y calcule los intervalos O (n).

O (N log N) + O (n) = O (n log n)

Answer 3

Ordenar todos los puntos. Luego vaya a la lista incrementando un contador para los puntos de "inicio" y disminuyéndolo para los puntos "finales". Si el contador llega a 0, entonces realmente es un punto final de uno de los intervalos en la unión.

El contador nunca irá negativo, y llegará a 0 al final de la lista.

Answer 4

El algoritmo por geocar falla cuando:

s=[tp(0,1),tp(0,3)] 

No estoy muy seguro, pero creo que esta es la forma correcta:

class tp(): 
    def __repr__(self): 
     return '(%.2f,%.2f)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(0,1),tp(0,3),tp(4,5)] 
s.sort(key=lambda self: self.start) 
print s 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 
    if x.end > y[-1].end: 
     y[-1].end = x.end 
print y 

También he implementado por la resta:

#subtraction 
z=tp(1.5,5) #interval to be subtracted 
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)] 

s.sort(key=lambda self: self.start) 
print s 
for x in s[:]: 
    if z.end < x.start: 
     break 
    elif z.start < x.start and z.end > x.start and z.end < x.end: 
     x.start=z.end 
    elif z.start < x.start and z.end > x.end: 
     s.remove(x) 
    elif z.start > x.start and z.end < x.end: 
     s.append(tp(x.start,z.start)) 
     s.append(tp(z.end,x.end)) 
     s.remove(x) 
    elif z.start > x.start and z.start < x.end and z.end > x.end: 
     x.end=z.start 
    elif z.start > x.end: 
     continue 

print s 

Answer 5

Resulta que esta p roblem ha sido resuelto, muchas veces - con distintos niveles de lujo, pasando por debajo de la nomenclatura (s): http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, y también 'RangeTree'

(como la pregunta de OP implica grandes cargos de intervalos de estas estructuras de datos importantes)

---

en términos de mi propia elección de selección de la biblioteca de Python:

• de las pruebas, estoy encontrando que lo que más lo clava en términos de ser completo actual ofrecido y un pitón (no poco descompuesto) : el ' Clases de intervalo y 'Unión' de SymPy, consulte: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Otra opción atractiva, una opción de mayor rendimiento pero con menos funciones (por ej. que no funcionó en el punto de extracción gama) flotando: https://pypi.python.org/pypi/Banyan

Por último: busca alrededor de SO en sí, bajo cualquiera de árbol de intervalo, ÁRBOL DE SEGMENTO, RangeTree, y encontrará respuestas/ganchos más abundancia

Answer 6

Para encontrar el total de la unión de intervalos en C++

#include <iostream> 
#include <algorithm> 

struct interval 
{ 
    int m_start; 
    int m_end; 
}; 

int main() 
{ 
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } }; 

    std::sort(
     arr, 
     arr + sizeof(arr)/sizeof(interval), 
     [](const auto& i, const auto& j) { return i.m_start < j.m_start; }); 

    int total = 0; 
    auto current = arr[0]; 
    for (const auto& i : arr) 
    { 
     if (i.m_start >= current.m_end) 
     { 
      total += current.m_end - current.m_start; 
      current = i; 
     } 
     else if (i.m_end > current.m_end) 
     { 
      current.m_end = i.m_end; 
     } 
    } 

    total += current.m_end - current.m_start; 
    std::cout << total << std::endl; 
}