Нахождение минимального расстояния в таблице

Question

У меня есть таблица размерности т * п, как указано ниже

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

Несколько ограничений об этой таблице:

1. элементов в каждой строке сортируется в порядке возрастания (натуральный заказ).
2. A -1 означает, что ячейка не имеет значения для целей calculatio, то есть элемент не существует.
3. Ни один элемент не может появляться в строке после -1.
4. Все ячейки могут иметь либо положительное число от 0 до N, либо a -1.
5. Нет двух ячеек с одинаковым положительным numbe, то есть -1 может отображаться несколько раз, но ни один другой номер не может.

Вопрос: Я хотел бы найти множество S из п чисел из таблицы, где набор должен содержать только один номер из каждой строки и Макса (S) - мин (S), настолько мал, насколько это возможно ,

Для примера. приведенная выше таблица дает мне S = 12,13,14.

Я был бы очень признателен, если это можно решить. Мое решение сложное, и оно занимает O(m^n), и это слишком много. Я хочу оптимальное решение.

Answer 1

1. Поместить позиции всех первых элементов каждой строки в очередь приоритетов (min-heap).
2. Удалите наименьший элемент из очереди и замените его следующим элементом из той же строки.
3. Повторите шаг 2, пока в строке не осталось больше элементов, отличных от «-1». Вычислите max (S) - min (S) для каждой итерации и, если он меньше любого предыдущего значения, обновите наилучшее расстояние S.

Сложность времени O (m * n * log (м)).

Answer 2

Вот перебор O((m*n)^2 * nlog(m)) алгоритм, который я могу доказать работы:

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

Объяснение:
Проверка, если есть число между а и Ь может быть сделано с помощью двоичного поиска, и O(logm)
Есть O((n*m)^2) различные возможности для a, b.

Идея состоит в том, чтобы исчерпывающе проверить пару, которая создает максимальную разницу, и проверить, дает ли она «выполнимое» решение (все остальные элементы в этом решении находятся в диапазоне [a, b]) и получают пару, которая минимизирует разницу между всеми «возможными» решениями.

---

EDIT: убрана 2-ое решение я предложил, который был жадным и неправильно.