Найдите пары идентификаторов из двух массивов, сумма которых меньше ближайшей к нему цели.

Имея два массива arr1[] и arr2[] пар вида {ID, значение} размера N и M соответственно и целочисленную цель , задача состоит в том, чтобы найти все пары идентификаторов из обоих массивов, такие что сумма значения пар максимальны и имеют значение не более M .

Примеры:

Input: arr1[] = [[1, 2000], [2, 3000], [3, 2000]], arr2[] = [[1, 2500], [2, 3000], [3, 3000]], target = 6000
Output:
2 2
2 3
Explanation:
Following are the pairs of elements from the two arrays arr1[] and arr2[]:

• (arr1[2], arr2[2]): The sum of elements 3000 + 3000 = 6000(= target) and closest to the value target. Print the IDs as (2, 2).
• (arr1[2], arr2[3]): The sum of elements 3000 + 3000 = 6000(= target) and closest to the value target. Print the IDs as (2, 3).

Input: arr1[] = [[1, 2000], [2, 3000], [3, 2000]], arr2[] = [[1, 3000], [2, 3000]], target = 5500
Output:
1 1
1 2
3 1
3 2

Подход: данная проблема может быть решена с использованием структуры данных TreeMap для хранения элементов массива arr1[] и эффективного поиска пары для каждого элемента в другом массиве arr2[] . Ниже приведены шаги:

• Создайте TreeMap, где ключ — это значение элемента массива, а значение — список идентификаторов .
• Перебрать массив arr1[] и вставить его элементы в TreeMap.
• Инициализируйте переменную, например, NearestTarget , чтобы отслеживать ближайшее значение к цели и не превышать ее.
• Инициализируйте результат ArrayList для хранения всех возможных пар идентификаторов.
• Переберите массив arr2[] и для каждого элемента вычислите оставшееся значение для поиска в TreeMap.
  • Если оставшееся значение, скажем, (цель — arr2[i]) меньше 0 , то пара не может быть сформирована, поэтому продолжайте итерацию.
  • Используйте функцию floorKey() в TreeMap, чтобы найти значение, меньшее или равное оставшемуся значению. Если возвращаемое значение вышеуказанной функции равно null , соответствующий элемент не найден.
  • Если возвращаемое значение, скажем, currentTarget больше, чем NearestTarget , тогда обновите ближайшийTarget и повторно инициализируйте результат[] массиваList в новый список.
  • Перебрать список идентификаторов, ключ которых является currentTarget , и добавить все возможные комбинации пар идентификаторов в список результатов .
• После выполнения вышеуказанных шагов выведите все пары идентификаторов, хранящихся в ArrayList result[] .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N + M)
Вспомогательное пространство: O(N*M)