cómo combinar de manera eficiente rangos int en una secuencia?

Question

Se nos da un flujo continuo de rangos enteros como [1,3], [5,10], [2,6], ... cuando llega cada nuevo rango, necesitamos verificar con los rangos existentes y ver si se superpone con cualquier rango existente, y si se encuentra una superposición, todos los rangos superpuestos se eliminan y el rango fusionado se inserta en su lugar. Necesitamos un algoritmo eficiente para esto. Tenga en cuenta que el rango viene uno a la vez y forma una secuencia ...

Se le hizo esta pregunta durante una entrevista. Ideas?

La intención es fusionar rangos superpuestos en uno. por ejemplo, si tenemos 3 rangos en el siguiente orden: [1,3], [2,6], [5,10]. Luego fusionamos primero los dos primeros en [1,6], luego nos fusionamos con el tercero y se convierte en [1,10].

Answer 1

Cuando una nueva tupla viene en (newstart,newend), realice una búsqueda binaria fon newstart-1 en la lista de elementos de cierre existentes y lo mismo para newend+1 en la lista de elementos de apertura existentes.

Combinar con cualquier rango coincidente.

Si no coincide el rango, inserte entre los dos rangos más cercanos.

Actualización: Rayo, estaba solucionando el problema equivocado: fusionar rangos de contacto. Pero la solución de rango superpuesto no será muy diferente.

1. La búsqueda binaria para el mayor elemento inicial existente donde start(n) <= newstart
2. La búsqueda binaria para el elemento que termina existente más pequeña, donde end(n) >= newstart
3. Si la vuelta dos el mismo índice, su inicio tupla puede fusionarse con la entrada de orden n, newstart reemplazar con start(n)
4. la búsqueda binaria para el mayor elemento inicial existente donde start(m) <= newend
5. la búsqueda binaria para el elemento más pequeño que termina existente donde end(m) >= newend
6. Si los dos regresan el mismo índice, su extremo tupla puede fusionarse con la entrada MTH, reemplace newend con end(m)
7. Reemplazar todas las entradas entre el índice de orden n y m-ésimo con el (newstart,newend) tupla.

Answer 2

Puede representar el rango como una secuencia única de alternar puntos "on" y "off". Cada vez que llega un nuevo rango, se buscan sus puntos de inicio y finalización y se toman las acciones apropiadas de fusión o inserción.

Con el fin de obtener un buen rendimiento para las operaciones requeridas — buscar, insertar y eliminar — uno podría utilizar algo así como un árbol B aquí.

Answer 3

El algoritmo estándar para este problema es interval tree.

Answer 4

Intervalo de servidor del árbol el propósito, pero aquí hay otro enfoque que he utilizado para agregar al rango.

Se asume que la lista a la que se agrega la nueva tupla (una línea) está vacía o no tiene rangos solapados.En segundo lugar, la entrada es de la forma a, b donde a < = b Puede convertir la lista de tuplas en una única lista de números y luego agregarle la nueva tupla.

Permitir rangeList ser la lista actual de rangos. p.ej. [1, 4, 6, 10, 12, 14] significaría una lista gama de [(1, 4), (6, 10), (12, 14)]

1. Si la lista está vacía, simplemente inserte los elementos de la tupla en la lista y ha terminado
2. Encuentre la posición del elemento a, b en la lista usando la búsqueda binaria. (Si el elemento no existe, devuelva la posición del elemento menos mayor que el número buscado)
3. Deje que las posiciones devueltas sean pos_a, pos_b para los elementos de la tupla a, b respectivamente.
4. Si pos_a es par, list_A = [a]
5. Si pos_b es par, list_B = [b]
6. La nueva lista = rangeList [0: pos_a] + list_A + list_B + rangeList [b: final] y has terminado.

Al convertir la lista de tuplas en una sola lista, eliminamos la necesidad de comparar los nuevos elementos con 2 listas diferentes. Encontrando así su posición fácilmente y verificando impar o par, nos dice si se encuentra entre un rango existente

def subroutine(rangeList, currTuple) 
""" 
rangeList: Existing list of non overlapping tuples 
currTuple: The range tuple to be added 
""" 
    if not rangeList: 
     rangeList.extend(currTuple) 
    else: 
     a, b = binSearch(currTuple, rangeList) 
     list_changed = rangeList[0:a] 
     if a%2 == 0: 
      list_changed.append(currTuple[0]) 
     if b%2 == 0: 
      list_changed.append(currTuple[1]) 
     list_changed.extend(rangeList[b:]) 
    return list_changed