查询以检查数字是否在C ++中的LR的N个范围内

在此问题中，我们给了N个范围[L，R]和Q个查询，每个查询都包含一个数字val。我们的任务是创建一个程序来解决查询，以检查数字是否在C ++中的LR的N个范围内。

问题描述

给定N个类型为[L，R]的范围，其中包含从L到R的整数值，例如，范围[3，6]包含3,4,5,6。在每个查询中，我们都将得到一个val，以检查其是否存在。如果val位于任一范围内，则程序将返回true，否则将返回false。

让我们举个例子来了解这个问题，

输入：ranges [N] = {{2，4}，{6,7}，{9，12}}

Q = 3

查询= {1，7，10}

输出：不存在

当下

当下

说明

对于查询1：1不在任何范围内。

对于查询2：数字7在{6，7}范围内。

对于查询1：数字10出现在{9，12}范围内。

解决方法

我们需要检查val是否存在于任何范围内，因此我们需要检查val与所有范围相对应。为此，我们将使用哈希映射。分别存储范围的L和R，然后使用二进制搜索算法进行搜索将使解决方案变得容易。

示例

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
   for (int i = 0; i < n; i++) {
      v.push_back(a[i][0]);
      mpp[a[i][0]] = 1;
      v.push_back(a[i][1]);
      mpp[a[i][1]] = 2;
   }
   sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
   int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
   if (v[ind] == val)
      return true;
   else {
      if (mpp[v[ind]] == 2)
         return true;
      else
         return false;
   }
}
int main(){
   int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
   int n = 3;
   int Q = 3;
   int query[] = { 1, 7, 10 };
   initialiseMap(arr, n);
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1);
      if(isElementPresent(query[i]))
         cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
      else
         cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
   }
   return 0;
}

输出结果

For Query 1: The given digit 1 is not present in any of the given ranges
For Query 2: The given digit 7 is present in one of the given ranges
For Query 3: The given digit 10 is present in one of the given ranges