Trovare la distanza minima in una tabella

Question

ho una tabella di dimensione m * n come indicato di seguito

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

pochi vincoli in questa tabella:

1. elementi in ciascuna fila sono ordinati in ordine crescente (ordinamento naturale ).
2. A -1 significa che la cella non ha alcun significato ai fini del calcolo di , cioè non esiste alcun elemento.
3. Nessun elemento può apparire in una riga dopo un -1.
4. Tutte le celle possono avere un numero positivo compreso tra 0 e N o a -1.
5. Nessuna cella ha lo stesso numero positivo, vale a dire un -1 può apparire più volte, ma nessun altro numero può.

Domanda: Vorrei trovare un insieme S di n numeri dalla tabella in cui l'insieme deve contenere un solo numero da ogni riga e massimo (S) - min (S) è il più piccolo possibile .

Ad es. la tabella sopra mi dà S = 12,13,14.

Apprezzerei molto se questo può essere risolto. La mia soluzione è complicata e ci vuole O(m^n) e questo è troppo. Voglio una soluzione ottimale.

Answer 1

1. Mettere le posizioni di tutti i primi elementi di ogni riga in coda di priorità (min-heap).
2. Rimuovi l'elemento più piccolo dalla coda e sostituirlo con l'elemento successivo della stessa riga.
3. Ripetere il passaggio 2 finché non vengono lasciati altri elementi diversi da "-1" in alcune righe. Calcola max (S) - min (S) per ogni iterazione e se è inferiore a qualsiasi valore precedente, aggiorna il set fino a oggi S.

La complessità del tempo è O (m * n * log (m)).

Answer 2

Ecco una forza bruta O((m*n)^2 * nlog(m)) algoritmo che posso dimostrare opere:

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|} 

Spiegazione:
controllare se v'è un numero compreso tra A e B può essere fatto utilizzando la ricerca binaria, ed è O(logm)
Ci sono O((n*m)^2) diverse possibilità per a, b.

L'idea è di controllare in modo esaustivo la coppia che crea la differenza massima e verificare se fornisce una soluzione "fattibile" (tutti gli altri elementi di questa soluzione sono nel range [a, b]) e ottenere la coppia che minimizza la differenza tra tutte le soluzioni "fattibili".

---

EDIT: rimossa la seconda soluzione che ho proposto, che era avido e sbagliato.