znalezienie minimalnej odległości w tabeli

Question

mam tabeli wymiar m * n, jak podano poniżej

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

pewnymi ograniczeniami o tej tabeli:

1. elementów w każdym rzędzie są sortowane w porządku rosnącym (Naturalne zamówienie ).
2. A-1 oznacza, że ​​komórka nie ma znaczenia dla celów obliczeń , tj. Żaden element tam nie istnieje.
3. Żaden element nie może pojawić się w wierszu po znaku -1.
4. Wszystkie komórki mogą mieć liczbę dodatnią między 0 a N lub a -1.
5. Żadna z dwóch komórek nie ma tej samej liczby dodatniej, tzn. -1 może pojawić się kilka razy, ale żadna inna liczba nie może być wyświetlana .

Pytanie: ja, aby znaleźć się zbiór S n numery z tabeli, w której zestaw może zawierać tylko jeden szereg z każdego rzędu i Maxa (S) - min (S) jest tak mały, jak to tylko możliwe .

Dla np. powyższa tabela daje mi S = 12,13,14.

Naprawdę doceniam, jeśli można to rozwiązać. Moje rozwiązanie jest skomplikowane i zajmuje O(m^n), a to za dużo. Chcę optymalnego rozwiązania.

Answer 1

1. Umieszcza pozycje wszystkich pierwszych elementów każdego wiersza w kolejce priorytetowej (min-sterty).
2. Usuń najmniejszy element z kolejki i zastąp go kolejnym elementem z tego samego wiersza.
3. Powtarzaj krok 2, aż w niektórych wierszach pozostanie więcej elementów niż "-1". Oblicz max (S) - min (S) dla każdej iteracji i jeśli jest mniejsza niż jakakolwiek poprzednia wartość, zaktualizuj najlepszy jak dotąd zbiór S.

Złożoność czasowa to O (m * n * log (m)).

Answer 2

Oto brute force O((m*n)^2 * nlog(m)) algorytm, że mogę udowodnić prace:

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

Objaśnienie:
sprawdzenie czy istnieje szereg pomiędzy A i B mogą być wykonane za pomocą wyszukiwania binarnego, i jest O(logm)
Istnieje O((n*m)^2) różnych możliwości dla a, b.

Chodzi o to, aby dokładnie sprawdzić parę, która tworzy maksymalną różnicę, i sprawdzić, czy daje "wykonalne" rozwiązanie (wszystkie pozostałe elementy tego rozwiązania znajdują się w zasięgu [a, b]) i uzyskać parę, która minimalizuje różnicę pomiędzy wszystkimi "wykonalnymi" rozwiązaniami.

---

EDIT: usunięto 2nd rozwiązanie zaproponowałem, który był chciwy i zły.