এই সমস্যায়, আমাদের একটি 2-D ম্যাট্রিক্স arr[][2] দেওয়া হয়েছে যা n রেঞ্জ (L, R), L-R নিয়ে গঠিত। এবং Q প্রশ্ন প্রতিটি একটি পূর্ণসংখ্যা মান নিয়ে গঠিত। আমাদের কাজ হল একটি সংখ্যা L-R-এর N রেঞ্জে আছে কিনা তা পরীক্ষা করার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − এখানে, আমরা প্রতিটি প্রশ্নের সমাধান করি যাতে প্রশ্নের প্রতিটি উপাদান যেকোন একটি রেঞ্জের মধ্যে থাকে।
তাদের রেঞ্জের ওভারল্যাপ করা যাবে না।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[n][2] = { {5, 7}, {1, 3}, {9, 12} } n = 3 Q = 2, query = {10, 4} আউটপুট
Yes No
ব্যাখ্যা
সমস্যা সমাধানের একটি সহজ উপায় হল প্রতিটি প্রশ্নের সমাধান করা এবং উপাদানগুলি যে পরিসরে রয়েছে তা খুঁজে বের করা। যদি এটি পরিসরের যেকোন একটিতে থাকে তবে সত্য ফেরত অন্যথা মিথ্যা ফেরত দিন। পরিসরের মানের উপর ভিত্তি করে ম্যাট্রিক্স বাছাই করা সাহায্য করতে পারে।
অ্যালগরিদম
ধাপ 1 − ম্যাট্রিক্সকে ক্রমানুসারে সাজান অর্থাৎ পরিসরের উপর ভিত্তি করে।
ধাপ 2 − i -> 0 থেকে Q, সমস্ত প্রশ্নের জন্য লুপ।
ধাপ 2.1৷ − যদি উপাদানটি যেকোনও পরিসরে থাকে, যেমন (arr[i][0] <=q &&arr[i][1]>=q) -> সত্য ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
