C++でN個の範囲の中で最も多く出現する整数を求める方法

問題概要

この問題では、N個の範囲（区間）が与えられ、その中で最も多く出現する整数を見つけることが課題となります。

各範囲には開始値と終了値が指定されており、これらすべての範囲を通して、最も多くの範囲に含まれる値を特定します。

入出力例

入力：

S1 = 1, E1 = 3
S2 = 2, E2 = 6
S3 = 3, E3 = 4

出力：

3

この例では、整数「3」が範囲 [1,3]、[2,6]、[3,4] のすべてに含まれており、合計3回出現するため、答えは 3 となります。

解法アプローチ

1. ハッシュテーブルを使う方法

最もシンプルな解法はハッシュ（連想配列）を利用する方法です。ハッシュテーブルですべての整数とその出現回数をカウントします。すべての範囲を走査しながら各整数の出現回数を記録し、その中から最大の出現回数を持つ値を探します。

2. 範囲配列と累積和を使う方法（線形時間）

線形時間 O(n) で解けるもう一つの効率的な方法が「範囲配列」を使う手法です。手順は以下の通りです。

• 各範囲の開始値に対応するインデックスに +1 を加算する。
• 各範囲の終了値 +1 に対応するインデックスから -1 を減算する。
• 配列全体の累積和（プレフィックスサム）を計算する。
• 累積和が最大になるインデックスが答えとなる。

この方法により、各位置を何個の範囲が覆っているかを効率的に求めることができます。

実装例

上記の解法を実装したC++プログラムは以下の通りです。

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;

int findMaxOccrEle(int L[], int R[], int n){
    int occurrenceCount[MAX];
    memset(occurrenceCount, 0, sizeof occurrenceCount);
    int maxi = -1;
    // 開始位置で +1、終了位置の次で -1 を設定
    for (int i = 0; i < n; i++) {
        occurrenceCount[L[i]] += 1;
        occurrenceCount[R[i] + 1] -= 1;
        if (R[i] > maxi) {
            maxi = R[i];
        }
    }
    // 累積和を計算し、最大値となるインデックスを求める
    int prefSum = occurrenceCount[0], maxEleIndex = 0;
    for (int i = 1; i < maxi + 1; i++) {
        occurrenceCount[i] += occurrenceCount[i - 1];
        if (prefSum < occurrenceCount[i]) {
            prefSum = occurrenceCount[i];
            maxEleIndex = i;
        }
    }
    return maxEleIndex;
}

int main(){
    int L[] = { 1, 2, 3 };
    int R[] = { 3, 6, 4 };
    int n = sizeof(L) / sizeof(L[0]);
    cout << "範囲内で最も多く出現する整数は " << findMaxOccrEle(L, R, n);
    return 0;
}

実行結果

範囲内で最も多く出現する整数は 3

計算量

時間計算量は O(n + MAX)、空間計算量は O(MAX) です（n は範囲の数、MAX は扱う値の上限）。範囲の数に対してほぼ線形時間で処理できるため、非常に効率的なアルゴリズムといえます。