C++で特定の値が含まれる区間の個数を数える方法

2次元配列 arr[][] には複数の区間（インターバル）が格納されており、それとは別に整数値 value が与えられます。この記事のゴールは、value が範囲内に含まれる区間の個数を求めることです。たとえば、区間が [ [1,5], [3,7] ] で value = 4 の場合、4 は両方の区間に含まれるため、答えは 2 になります。

入力例と出力例

例1

入力：

arr[4][2] = { { 1, 20 }, { 12, 25 }, { 32, 40 }, { 15, 18 } }, value = 16

出力：

指定した値が含まれる区間の数：3

説明：

値 16 は 1〜20、12〜25、15〜18 のいずれの区間にも含まれています。

例2

入力：

arr[4][2] = { { 1, 20 }, { 20, 30 }, { 30, 40 }, { 40, 50 } }, value = 60

出力：

指定した値が含まれる区間の数：0

説明：

値 60 は arr[][] に存在するすべての区間の最大値よりも大きいため、どの区間にも含まれません。

使用するアプローチ

この問題では、差分配列（いもす法）として知られる累積和のテクニックを使用します。各区間について始点と「終点+1」の位置だけを目印として記録し、最後に累積和を取ることで、各位置がいくつの区間に含まれているかを効率的に求められます。具体的には、区間 arr[i][0]〜arr[i][1] ごとに arr_2[arr[i][0]] を +1、arr_2[arr[i][1] + 1] を −1 します。その後、arr_2[i] = arr_2[i] + arr_2[i − 1] という累積和の計算を行うことで、「i より前の数が含まれる区間の個数」が「i が含まれる区間の個数」に反映され、最終的に arr_2[value] が value を含む区間の総数になります。

アルゴリズムの手順

• 区間を格納する整数型の2次元配列 arr[][] を用意します。
• 調べたい整数値 value を入力として受け取ります。
• 関数 intervals_values(int arr[][2], int size, int value) は、arr と value を引数に取り、value が含まれる区間の個数を返します。
• 頻度配列（差分配列）arr_2[] を用意し、すべての要素を 0 で初期化します。
• low に INT_MAX、highest に INT_MIN を設定します。
• for ループを使って、i = 0 から i < size まで arr[][] を走査します。
• 区間の左端を temp として取り、arr_2[temp] をインクリメントします。
• 区間の右端を temp_2 として取り、arr_2[temp_2 + 1] をデクリメントします。
• temp < low であれば low = temp とし、temp_2 > highest であれば highest = temp_2 と更新します。
• 頻度配列を走査し、arr_2[i] = arr_2[i] + arr_2[i − 1] として累積和を計算します。
• 最後に arr_2[value] を結果として返します。

C++実装例

#include<bits/stdc++.h>
using namespace std;
#define max 1000

int intervals_values(int arr[][2], int size, int value){
    int arr_2[max] = { 0 };   // ローカル配列は必ずゼロで初期化する
    int low = INT_MAX;
    int highest = INT_MIN;

    for(int i = 0; i < size; i++){
        int temp = arr[i][0];
        arr_2[temp]++;          // 始点で +1
        int temp_2 = arr[i][1];
        arr_2[temp_2 + 1]--;    // 終点+1 で -1

        if(temp < low){
            low = temp;
        }
        if(temp_2 > highest){
            highest = temp_2;
        }
    }

    // 累積和を計算して、各区間に含まれる個数へ変換する
    for(int i = low + 1; i <= highest; i++){
        arr_2[i] = arr_2[i] + arr_2[i - 1];
    }

    return arr_2[value];
}

int main(){
    int arr[4][2] = { { 3, 20 }, { 2, 13 }, { 25, 30 }, { 15, 40 } };
    int size = sizeof(arr) / sizeof(arr[0]);
    int value = 28;

    cout << "指定した値が含まれる区間の数: "
         << intervals_values(arr, size, value);

    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

指定した値が含まれる区間の数: 2

値 28 は区間 25〜30 と 15〜40 の2つの区間に含まれるため、正しく 2 が出力されます。

注意点と計算量

配列 arr_2 は関数内のローカル変数であるため、{ 0 } などで明示的に初期化しないと不定値（ゴミ値）が残り、誤った結果が出力される可能性があります。また、このアルゴリズムの時間計算量は、区間の個数を n、値域のサイズを R として O(n + R)、空間計算量は O(R) です。区間の数が多くても高速に動作するのがこの手法の大きな利点です。