Truy vấn để kiểm tra xem một số có nằm trong N dãy L-R trong C ++ hay không

Trong bài toán này, chúng ta có N dãy [L, R] và Q truy vấn, mỗi truy vấn chứa một số val. Nhiệm vụ của chúng ta là tạo một chương trình giải các Truy vấn để kiểm tra xem một số có nằm trong N dãy L-R trong C ++ hay không.

Mô tả vấn đề

Chúng ta được cung cấp cho N dãy kiểu [L, R] chứa các giá trị lớn hơn từ L đến R, ví dụ, dãy [3, 6] chứa 3,4,5,6. Bất cứ truy vấn nào, chúng tôi đều nhận được một giá trị, mà sự hiện diện của nó sẽ được kiểm tra. Chương trình sẽ trả về true nếu giá trị có trong bất kỳ một trong các phạm vi, ngược lại, nó sẽ trả về false.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :range [N] ={{2, 4}, {6,7}, {9, 12}}

Q =3

Truy vấn ={1, 7, 10}

Đầu ra :Không có mặt

Hiện tại

Hiện tại

Giải thích

Đối với truy vấn 1:số 1 không có trong bất kỳ phạm vi nào.

Đối với truy vấn 2:số 7 có trong phạm vi {6, 7}.

Đối với truy vấn 1:số 10 có trong phạm vi {9, 12}.

Phương pháp tiếp cận giải pháp

Chúng ta cần kiểm tra xem giá trị có ở bất kỳ phạm vi nào hay không, vì vậy chúng ta cần kiểm tra xem giá trị đó có tương ứng với tất cả các phạm vi hay không. Đối với điều này, chúng tôi sẽ sử dụng một bản đồ băm. Việc sắp xếp L và R của phạm vi một cách riêng biệt và sau đó tìm kiếm bằng các thuật toán tìm kiếm nhị phân sẽ dễ dàng đưa ra giải pháp.

Ví dụ

#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;
}

Đầu ra

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