Максимальное количество пар из двух отсортированных массивов

Question

Это не оригинальная проблема.У меня была сложная проблема, которая теперь сводится к следующему:

Есть два отсортированных массива, A и B с m и n элементами соответственно, m = \Theta(n) Может алгоритм, которыйработает за o(mn) время, найдите максимальное количество пар, такое что A[i]-B[j] <= T где T - некоторая постоянная?Как это может быть сделано?

edit:

1. Пары должны быть непересекающимися, то есть один элемент может быть выбран не более одного раза.

2. Алгоритм должен работать в little-o (mn), что означает, что решение, выполняемое за mn, неприемлемо.

3. Можно ли найти пары, которые мы выбрали?

Уточнение:

Если массивы a_1, a_2, ..., a_m и b_1, b_2, ..., b_n, мне нужно найти пары (a_i, b_j) такие, что |a_i - b_j| <= T.Не разрешается выбирать элемент более одного раза.Как мы можем максимизировать количество пар с учетом массивов?

Answer 1

ОБНОВЛЕНИЕ 2:

Обновленный вопрос (используйте элемент из любого массива только один раз, получите пары, и абсолютная разница значений должна быть ниже T), возможно,быть в состоянии сделать за O (n + m) время.Я не продумал алгоритм ниже, чтобы решить, будет ли он всегда получать максимальное количество пар или нет, но в большинстве случаев так и должно быть:

int i = 0;
int j = 0; 

while(i < A.length){
    while(j < B.length){
        if(A[i]-B[j] <= T){
            if(A[i]-B[j] >= -1 * T){
                addPair(i, j);
                j++;//don't consider this value the next time
            }
            break;
        } 
        j++;
    }
    i++;
}

Answer 2

In O(n lg n) = O(m lg m): Создать сбалансированное двоичное дерево поиска из элементов A и сохранить в каждом узле индекс элемента вместе со значением элемента. Для каждого элемента B найдите наибольшее значение, которое меньше или равно B[j] + T. Индекс этого числа скажет вам, сколько чисел меньше или равно этому числу.

Answer 3

Если вы хотите, чтобы количество пар соответствовало |A[i]-B[j]| <= T, где каждый A[i] и B[j] используется только один раз во всех парах:

int lastB = 0;
int result=0;
for(int a = 0; a<A.size(); ++a) {
    const int minB = A[a] - T;  
    while(lastB<B.size() && B[lastB] < minB)
        ++lastB;
    const int maxB = A[a] + T;
    if (lastB<B.size() && B[lastB] > minB) {
        ++lastB;
        ++result;
    }
}
return result;

Этот алгоритм сканирует минимальные диапазоны в Bи следит за тем, чтобы ни один элемент в B не использовался дважды.