C++の2つのアレイからの一意のペアの最大化

問題の説明

サイズNが等しい2つの配列が与えられた場合、それらの要素を使用して最大数のペアを形成します。1つは最初の配列から、2つ目は2番目の配列から、各配列の要素が最大1回使用され、選択されたものの絶対差が使用されます。ペアを形成するために使用される要素は、特定の要素K以下です。

例

入力が-

arr1 [] ={3、4、5、2、1}

arr2 [] ={6、5、4、7、15}

k =3の場合、絶対差が3 −

（1、4）、（2、5）、（3、6）、（4、7）

アルゴリズム

この問題を解決するために再帰的アプローチを使用できます

• 両方のアレイを並べ替える
• ペアを形成できる場合は、最初の配列の各要素を2番目の配列の各要素と比較して、可能なペアを探します。
• 最初の配列の次の要素の次の可能なペアを引き続き確認します。

例

例を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
   sort(arr1, arr1 + n);
   sort(arr2, arr2 + n);
   bool visited[n];
   memset(visited, false, sizeof(visited));
   int pairCnt = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
         if (abs(arr1[i] - arr2[j]) <= k &&
         visited[j] == false) {
            ++pairCnt;
            visited[j] = true;
            break;
         }
      }
   }
   return pairCnt;
}
int main() {
   int arr1[] = {3, 4, 5, 2, 1};
   int arr2[] = {6, 5, 4, 7, 15};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int k = 3;
   cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
   return 0;
}

出力

Maximum unique pairs = 4