Выбрать из 4-х массивов по элементу с минимальной разницей между наибольшим и наименьшим из них

Даны 4 массива, надо выбрать из каждого из них по одному числу x_i, чтобы разница между x_min и x_max (наиб. и наим. среди 4х выбранных элементов x_i) была минимальной. Если таких наборов несколько, можно использовать любой из них.
Сложности возникли не с реализацией, а с созданием алгоритма. Я хотел использовать жадный алгоритм, но не могу понять, как может помочь для получения ответа решение подзадач для двух массивов.
UPD : Написал алгоритм, работает верно, но не проходит по времени. Не из-за того-ли что я вынес поиск ближайшего элемента в отдельную функцию dist и вызываю ее потом по три раза на каждую группу?
int dist(const std::vector& A, int x) { int sec = binary_search(A, x), ans; if (sec == 0) { ans = 0; } else if (sec == A.size()) { ans = sec - 1; } else if ((abs(A[sec] - x) < abs(A[sec - 1] - x))) { ans = sec; } else { ans = sec - 1; } return ans; }
int diff(const std::vector& A) { return *std::max_element(A.begin(), A.end()) - *std::min_element(A.begin(), A.end()); } int main() { // здесь считываю, сортирую вектора. std::vector ans(4); int min = 100000000000; for (int i = 0; i != n1; i++) { //прохожусь по первому for (int i2 = 0; i2 <= 2; ++i2) { //рассматриваю 2^3 смежных случаев for (int i3 = 0; i3 <= 2; ++i3) { for (int i4 = 0; i4 <= 2; ++i4) { std::vector temp(4); temp[0] = v1[i]; //здесь рассматриваю случаи, чтобы не было выходов за вектор temp[1] = v2[i_2 - 1 + dist(v2, v1[i])]; temp[2] = v3[i_3 - 1 + dist(v3, v1[i])]; temp[3] = v4[i_4 - 1 + dist(v4, v1[i])]; if (diff(temp) < min) { min = diff(temp); ans = temp; } } } } } for (auto elem : ans) { std::cout << elem << " "; } return 0;
}

Ответ

По идее, должна сработать следующая идея: вы просто обобщаете алгоритм для двух массивов на более общий случай.
Например, так:
Сортируете все массивы. Проходитесь по первому массиву. Запоминаете текущий индекс 0 во всех 4 массивах. На каждом шагу, продвигаете индекс в первом массиве, и находите ближайший элемент к нему во остальных массиве. Для этого вам придётся продвинуться вперёд в этих массивах. При этом вы получаете для каждого из массивов ближайший элемент к элементу первого массива.
На этом шаге мы ищем группу элементов с оптимальным расстоянием между ними, которая включает данный элемент первого массива Это ещё не гарантирует, что мы нашли оптимум. Нам нужно перебрать 2^3 вариантов из { «ближайший снизу», «ближайший сверху» } для каждого из массивов, каждый из них может дать оптимум. Находите расстояние между наибольшим и наименьшим из них. Сравниваете его с текущим максимумом и продвигаетесь дальше по первому массиву.
Мы проходимся по каждому из массивов один раз, общая асимптотика — сумма длин массивов.