2011-01-20 12 views
7

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 ...cómo combinar de manera eficiente rangos int en 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].

+0

Su pregunta no está clara. ¿Desea que la salida sea una secuencia única como [1,2,3,5,6,7,8,9,10,2,3,4,5,6]? –

+0

@Jim Mischel: suponía que cada tupla proporcionaba un inicio y un final de rango, por lo tanto, después de la primera tupla, el rango resultante incluiría [1,2,3]. Después de la segunda tupla, el rango resultante sería [1,2,3,5,6,7,8,9,10] (no 4). – oosterwal

+2

a mis ojos, una salida lógica posible debería ser una lista de rangos (ordenados) que fusionan rangos de solapamiento – kriss

Respuesta

0

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.
+0

Eso es similar a mi respuesta durante la entrevista. El problema con esto es que crea gradualmente entradas duplicadas en el paso 7, que a medida que pasa el tiempo provocará un desperdicio de espacios. – Robin

+0

@Robin ¿Entradas duplicadas? ¿Dónde? – biziclop

+0

búsqueda binaria es log (n), pero qué estructura de datos para fusionar intervalos. La matriz que elimina un intervalo toma O (n). La lista vinculada no puede funcionar para la búsqueda binaria. –

0

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í.

9

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

+0

Gracias. Simplemente eché un vistazo al árbol de intervalos, y aunque solo requiere el tiempo O (logn) cuando busco una entrada solapada para un nuevo rango, insertar un nuevo rango podría superponerse con muchas entradas en el árbol, haciendo que todas sean borrado El costo de eliminar estas entradas superpuestas y girar el árbol a un estado equilibrado no sería trival. ¿O me estoy perdiendo algo? – Robin

+0

Sí, insertar un nuevo rango puede dar como resultado la eliminación de muchos otros rangos, pero puede amortizar ese costo contra el costo de insertar esos otros rangos en primer lugar. No he pensado en mantener el árbol equilibrado, pero imagino que hay una manera de hacerlo en AVL o árboles rojo-negro. –

0

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 
Cuestiones relacionadas