c++ – Select from 4 arrays by element with the minimum difference between the largest and smallest of them

Question:

Given 4 arrays, you need to choose from each of them one number x_i so that the difference between x_min and x_max (the most and the least among the 4 selected elements x_i) was minimal. If there are several such sets, you can use any of them.

The difficulties arose not with the implementation, but with the creation of the algorithm. I wanted to use a greedy algorithm, but I cannot figure out how a solution of subproblems for two arrays can help to get an answer.

UPD: I wrote an algorithm, it works correctly, but does not pass in time. Is it because I moved the search for the nearest element into a separate dist function and then call it three times for each group?

int dist(const std::vector<int>& 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<int>& A) {
    return *std::max_element(A.begin(), A.end()) - *std::min_element(A.begin(), A.end());
}
int main() {
    // здесь считываю, сортирую вектора.
    std::vector<int> 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<int> 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;

}

Answer:

In theory, the following idea should work: you simply generalize the algorithm for two arrays to a more general case.

For example, like this:

1. Sort all arrays.
2. Step over the first array. Remember the current index 0 in all 4 arrays.
3. At each step, advance the index in the first array, and find the closest element to it in the rest of the array. To do this, you have to move forward in these arrays. In doing so, you get for each of the arrays the closest element to the element of the first array.
   • In this step, we are looking for a group of elements with an optimal distance between them, which includes the given element of the first array .
   • This does not yet guarantee that we have found the optimum. We need to iterate over 2 ^ 3 options from {"closest from the bottom", "closest from the top"} for each of the arrays, each of them can give the optimum.
4. Find the distance between the largest and smallest of them. Compare it with the current maximum and move further along the first array.

We go through each of the arrays once, the total asymptotics is the sum of the lengths of the arrays.