C++で区間内に最も頻繁に出現する数を求める方法

問題の概要

整数の区間を表すリストのリストが与えられます。各要素は [start, end] のような形式の区間です。この中から、最も多くの区間に含まれる数（最頻出数）を見つける必要があります。複数の候補が同数の場合は、その中で最も小さい数を返します。

たとえば、入力が [[2, 5], [4, 6], [7, 10], [8, 10]] の場合、出力は 4 になります。

解法のアプローチ

この問題は、いもす法（差分配列）として知られる手法を使うと効率的に解けます。各区間 [start, end] について、開始位置でカウントを +1、終了位置の次の位置で -1 します。その後、キーを昇順に走査しながら累積和を計算すると、各位置が何個の区間に覆われているかが分かります。

std::map を使うとキーが自動的に昇順でソートされるため、同数の場合も自然と最も小さい数が選ばれる点がポイントです。

アルゴリズムの手順

• マップ m を定義します。
• cnt := 0、val := 0 と初期化します。
• x 内の各区間 it に対して以下を実行します。
  • m[it[0]] を 1 増やします。
  • m[it[1] + 1] を 1 減らします。
• last := 0 と初期化します。
• m の各キー it に対して以下を実行します。
  • last にそのキーの値を加算します（累積和の更新）。
  • last > cnt の場合は、cnt := last、val := it と更新します。
• val を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<vector<int>>& x) {
        map <int, int> m;
        int cnt = 0;
        int val = 0;
        for(auto& it : x){
            m[it[0]]++;
            m[it[1] + 1]--;
        }
        int last = 0;
        for(auto& it : m){
            last += it.second;
            if(last > cnt){
                cnt = last;
                val = it.first;
            }
        }
        return val;
    }
};
main() {
    Solution ob;
    vector<vector<int>> v = {{2, 5},{4, 6},{7, 10},{8, 10}};
    cout << ob.solve(v);
}

入力

{{2, 5},{4, 6},{7, 10},{8, 10}}

出力

4

動作の解説

この入力の場合、マップは次のようになります。

m = {2: +1, 4: +1, 6: -1, 7: 0, 8: +1, 11: -2}

キーを昇順に走査して累積和を計算すると、位置 2 で 1、位置 4 で 2 となり、cnt = 2、val = 4 が記録されます。位置 8 でも累積和は 2 になりますが、last > cnt が成立しないため、より小さい 4 が答えとして保持されます。これにより「同数の場合は最小の数を返す」という条件が自動的に満たされます。

計算量

• 時間計算量： O(n log n) — n 個の区間に対するマップへの挿入と走査がボトルネックです。
• 空間計算量： O(n) — マップに格納されるキーの数に依存します。