C++で2つの配列から作れるペアの最大数を求めるアルゴリズム

問題の概要

同じサイズ N を持つ2つの配列が与えられたとき、各配列から1つずつ要素を選んでペアを作り、そのペアの最大数を求めます。ただし、以下の条件を満たす必要があります。

• 各配列の要素は最大1回しか使用できない
• ペアを構成する2つの要素の絶対差が指定された値 K 以下であること

入力例

たとえば、次のような入力が与えられたとします。

arr1[] = {3, 4, 5, 2, 1}
arr2[] = {6, 5, 4, 7, 15}
k = 3

この場合、絶対差が3以下になるペアは次の4組です。

(1, 4), (2, 5), (3, 6), (4, 7)

したがって、答えは 4 となります。

アルゴリズムの考え方

この問題は、貪欲法（グリーディー法）に基づくシンプルな反復処理で解くことができます。

1. 両方の配列を昇順にソートする — 小さい要素同士から順にマッチングを試みることで、効率よくペアを見つけられます。
2. 第1配列の各要素について、第2配列の未使用要素と比較する — 絶対差が K 以下であればペアとして成立します。
3. ペアが成立したら、使用済みフラグを立てて次へ進む — 各要素は1回しか使えないため、bool 型の配列で使用状況を管理します。

C++での実装例

それでは、実際のコードを見てみましょう。

#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

計算量について

この実装では二重ループを使用しているため、時間計算量は O(N²) となります。N が大きい場合は、ソート後に両配列を先頭から順に走査し、条件を満たす要素までポインタを進めていく「二ポインタ（two-pointer）」手法を使うことで、O(N log N)（ソート込み）まで高速化できます。

まとめ

2つの配列から絶対差 K 以下のペアを最大化する問題は、ソートと貪欲なマッチングを組み合わせることで簡潔に解決できます。要素の再利用を防ぐために visited フラグで管理する点がポイントです。より大規模な入力に対応したい場合は、二ポインタ方式への置き換えも検討してみてください。