【C++】数値が複数の区間(L〜R)に含まれるかどうかを判定するクエリ処理

問題概要

この問題では、n 個の区間 (L, R) を格納した2次元配列 arr[][2] と、整数値からなる Q 個のクエリが与えられます。各クエリで指定された数値が、いずれかの区間内に存在するかどうかを判定するプログラムを作成するのが課題です。

問題の詳細： 各クエリについて、その数値が与えられた区間のいずれかに含まれるかを確認し、結果を出力します。

なお、区間同士が重複（オーバーラップ）することはないものとします。

入力例

arr[n][2] = { {5, 7}, {1, 3}, {9, 12} }
n = 3
Q = 2
query = {10, 4}

出力例

Yes
No

解説

クエリ1の「10」は区間 {9, 12} に含まれるため「Yes」、クエリ2の「4」はどの区間にも含まれないため「No」となります。

解法のアプローチ

最もシンプルな方法は、各クエリに対してすべての区間を順番に調べ、その数値が含まれる区間が存在するかを確認することです。条件を満たす区間が見つかれば true を返し、最後まで見つからなければ false を返します。あらかじめ配列を区間の開始値を基準にソートしておくことで、探索を効率化できます。

アルゴリズム

ステップ1： 区間の開始値を基準に、配列を行単位でソートします。

ステップ2： i を 0 から Q までループさせ、すべてのクエリを処理します。

ステップ2.1： 数値がいずれかの区間に含まれる場合（arr[i][0] <= q かつ arr[i][1] >= q）、true を返します。

C++実装例

以下は、この解法の動作を示すプログラムです。

#include <iostream>
using namespace std;
bool isPresent(int arr[][2], int n, int element){
    for(int i = 0; i < n; i++){
       if(arr[i][0] <= element && arr[i][1] >= element )
       return true;
    }
    return false;
}
void solveQueries_Range(int arr[][2], int n, int Q, int query[]){
    int temp[2];
    for(int j = 0; j < (n - 1); j++){
       for(int k = (j + 1); k < n; k++)
       if(arr[j][0] > arr[k][0]){
          temp[0] = arr[k][0]; temp[1] = arr[k][1];
          arr[k][0] = arr[j][0]; arr[k][1] = arr[j][1];
          arr[j][0] = temp[0]; arr[j][1] = temp[1];
       }
    }
    for(int i = 0; i < Q; i++ ){
       if(isPresent(arr, n, query[i]))
          cout<<"For Query "<<(i + 1)<<": The number "<<query[i]<<" lies in the range\n";
       else
          cout<<"For Query "<<(i + 1)<<": The number "<<query[i]<<" does not lie in the range\n";
    }
}
int main(){
    int arr[][2] = { {5, 7}, {1, 3}, {9, 12} };
    int n = 3;
    int Q = 2;
    int query[] = { 10, 4 };
    solveQueries_Range(arr, n, Q, query);
    return 0;
}

出力結果

For Query 1: The number 10 lies in the range
For Query 2: The number 4 does not lie in the range

実行結果から、クエリ1の数値「10」は区間内に存在し、クエリ2の数値「4」はどの区間にも含まれていないことがわかります。

計算量と改善のポイント

上記の実装では、ソートに O(n²)（バブルソート的な交換を使用）、各クエリの判定に O(n) かかるため、全体の時間計算量は O(n² + Q×n) となります。

区間がソート済みで重複しないという性質を利用すると、std::sort（O(n log n)）や二分探索（クエリごとに O(log n)）を用いることで、さらに効率的な実装が可能です。クエリ数や区間数が多い場合は、これらの標準ライブラリを活用することをおすすめします。