इस समस्या में, हमें एक 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