C++で与えられた点を含むことができる線分の最大数を求めるアルゴリズム

この記事では、「与えられた複数の点を含むことができる線分の数」の最大値を求める問題について解説します。

問題概要

サイズ n1 の配列 a1[] と、2つの整数 A・B が与えられます。配列 a1[] の各要素からは、始点を a1[i] − A、終点を a1[i] + B とする n1 個の線分を作成できます。

さらに、n2 個の点からなる別の配列 a2[] が与えられます。これらの点を各線分に割り当てるとき、点が割り当てられた線分の数を最大化することが目標です。なお、1つの点を同じ線分に複数回割り当てることはできません。

具体例で理解しよう

入力例 1

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

出力例 1

1

説明: 点 a1[i] − A と a1[i] + B から作成できる線分は (0, 6) と (3, 7) の2本です。

配列 a2[] の最初の点「2」は最初の線分 (0, 6) に割り当てられますが、次の点「8」はどの線分にも含まれません。したがって、点を割り当てられる線分は1本だけで、出力は 1 となります。

入力例 2

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

出力例 2

4

アルゴリズム(貪欲法)

この問題は、両方の配列をあらかじめソートしておき、貪欲法(Greedy法)で効率よく解くことができます。手順は以下の通りです。

• main 関数内で、ベクトル a1・a2 および整数 A・B を所定の値で初期化します。
• 変数 n1・n2 を作成し、それぞれベクトル a1・a2 のサイズを格納します。
• Max() 関数内で、まず両方のベクトル a1・a2 をソートします。
• ベクトル a2 の位置を追跡するために j = 0、最終的な答えを保持するために ans = 0 を初期化します。
• i = 0 から i < n1 まで for ループを回します。
• for ループの中で、条件 j < n2 を持つ while ループを開始します。
• (a1[i] + B < a2[j]) の場合、現在の線分の終点が対象の点より手前にあるため、while ループを抜けます。
• それ以外の場合、(a2[j] >= a1[i] − A && a2[j] <= a1[i] + B) かどうかを判定します。真であれば点をこの線分に割り当てられるので、ans と j をインクリメントし、while ループを抜けます。
• どちらの条件も満たさない場合は、j をインクリメントして次の点へ進みます。
• すべての処理が完了したら ans を返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
    // a1 と a2 をソート
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());
    int j = 0;
    int ans = 0;
    for (int i = 0; i < n1; i++){
        // 点を探索
        while (j < n2){
            /* 線分の終点が現在の点より小さい場合 */
            if (a1[i] + B < a2[j])
                break;
            // 点が線分の範囲内にある場合
            if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){
                ans++;
                j++;
                break;
            }
            else
                j++;
        }
    }
    return ans;
}
// main 関数
int main(){
    int A = 0, B = 1;
    vector<int> a1 = { 1, 2, 3, 4, 6, 7 };
    int n1 = a1.size();
    vector<int> a2 = { 2, 5, 6, 8 };
    int n2 = a2.size();
    cout << Max(a1, a2, n1, n2, A, B);
    return 0;
}

出力

4

計算量の評価

両方の配列のソートに O(n1 log n1 + n2 log n2) の計算量が必要です。その後の二重ループでは、内側の while ループのポインタ j が後が後戻りしないため、各点は高々1度しか処理されず、O(n1 + n2) で完了します。全体の時間計算量は O(n1 log n1 + n2 log n2)、空間計算量は O(1)(入力を除く)となります。