C++で指定されたN個の整数のうちちょうど1つだけを含む最大区間を求める方法

問題概要

N個の相異なる整数からなる配列が与えられたとします。このとき、与えられたN個の整数のうちちょうど1つだけを含み、かつ 1 ≤ L ≤ R ≤ 10⁵ を満たす区間 [L, R] の中から、最も多くの整数を含む（＝最も長い）区間を見つける必要があります。

例として、配列が Arr = [5, 10, 200] の場合を考えてみましょう。このときの出力は 99990 となります。候補となる区間は [1, 9]、[6, 199]、[11, 100000] の3つで、それぞれ 5、10、200 をちょうど1つずつ含みます。この中で最後の区間 [11, 100000] には 99990 個の整数が含まれており、これが最大値になります。

アルゴリズムの考え方

発想はシンプルです。まず、区間に含めたい要素を1つ固定し、他の要素と重ならないように、その区間を左方向・右方向へどこまで伸ばせるかを調べます。

具体的な手順は以下の通りです。

• 配列をあらかじめ昇順にソートしておきます。
• 番兵（sentinel）として 0 と 100001 を配列の先頭と末尾に追加します。これにより、最小値や最大値を固定する場合などの境界ケースを特別な分岐なしに統一的に扱えます。
• ソート後の各要素 vec[i] について、区間の左端は「直前の要素 + 1」（vec[i-1] + 1）、右端は「直後の要素 − 1」（vec[i+1] − 1）として決定します。
• 各区間の長さ（Right − Left + 1）を計算し、その最大値を答えとして返します。

この方法により、すべての要素 i に対して、その要素を唯一含む区間の最大長を効率よく求めることができます。

C++での実装例

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int maximumSize(vector<int>& vec, int n) {
    vec.push_back(0);
    vec.push_back(100001);
    n += 2;
    sort(vec.begin(), vec.end());
    int max_value = 0;
    for (int i = 1; i < n - 1; i++) {
        int Left = vec[i - 1] + 1;
        int Right = vec[i + 1] - 1;
        int count = Right - Left + 1;
        max_value = max(max_value, count);
    }
    return max_value;
}
int main() {
    vector<int> v;
    v.push_back(200);
    v.push_back(10);
    v.push_back(5);
    int n = v.size();
    cout << "Maximum Size is: " << maximumSize(v, n);
}

実行結果

Maximum Size is: 99990

計算量

ソートに O(N log N)、各区間の長さの計算に O(N) かかるため、全体の時間計算量は O(N log N) です。メモリについても、番兵2つ分の追加だけで済むため、空間計算量は O(N) と非常に効率的です。