Encontrar la distancia mínima en una mesa

Question

I tienen una tabla de dimensión m * n como se indica a continuación

2 6 9 13 
1 4 12 21 
10 14 16 -1 

pocas restricciones sobre esta tabla:

1. elementos en cada fila se clasifican en orden creciente (pedido natural ).
2. A -1 significa que la celda no tiene importancia para el propósito del cálculo , es decir, no existe ningún elemento allí.
3. Ningún elemento puede aparecer en una fila después de -1.
4. Todas las celdas pueden tener un número positivo entre 0 y N o a -1.
5. No hay dos celdas que tengan el mismo número positivo, es decir, un -1 puede aparecer varias veces pero ningún otro número puede hacerlo.

Pregunta: Me gustaría encontrar un conjunto S de n números de la tabla, donde el conjunto debe contener sólo un número de cada fila y máximo (S) - min (S) es lo más pequeño posible .

Por ej. la tabla anterior me da S = 12,13,14.

Realmente apreciaría si esto puede ser resuelto. Mi solución es complicada y toma O(m^n) y esto es demasiado. Quiero una solución óptima.

Answer 1

1. Coloque las posiciones de todos los primeros elementos de cada fila en la cola de prioridad (min-heap).
2. Quite el elemento más pequeño de la cola y reemplácelo con el siguiente elemento de la misma fila.
3. Repita el paso 2 hasta que no queden más elementos diferentes de "-1" en alguna fila. Calcule max (S) - min (S) para cada iteración y si es más pequeño que cualquier valor anterior, actualice el conjunto mejor hasta ahora. S.

La complejidad del tiempo es O (m * n * log (metro)).

Answer 2

Aquí es una fuerza bruta O((m*n)^2 * nlog(m)) algoritmo que puedo demostrar obras:

min <- INFINITY 
For each 2 numbers in different rows, let them be a,b 
    for each other row: 
     check if there is a number between a and b 
    if there is a matching number in every other row: 
     min <- min{min,|a-b|} 

Explicación:
Comprobación de si hay un número entre A y B se puede hacer mediante la búsqueda binaria, y es O(logm)
Hay O((n*m)^2) diferentes posibilidades para a, b.

La idea es comprobar exhaustivamente el par que crea la diferencia máxima, y ​​comprobar si proporciona una solución "factible" (todos los demás elementos de esta solución están en el rango [a, b]), y obtener el par minimiza la diferencia entre todas las soluciones "factibles".

---

EDITAR: retira la segunda solución que propuse, que era codicioso y el mal.