ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติ arr[][2] ที่ประกอบด้วย n ช่วง (L, R), LR และ Q เคียวรีแต่ละรายการประกอบด้วยค่าจำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อแก้ปัญหาแบบสอบถามเพื่อตรวจสอบว่าตัวเลขอยู่ในช่วง N ของ L-R หรือไม่
คำอธิบายปัญหา − ที่นี่ เราแก้ไขการสืบค้นข้อมูลแต่ละรายการ โดยให้แต่ละองค์ประกอบของข้อความค้นหาอยู่ในช่วงใดช่วงหนึ่ง
ไม่สามารถซ้อนทับช่วงได้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[n][2] = { {5, 7}, {1, 3}, {9, 12} } n = 3 Q = 2, query = {10, 4} ผลลัพธ์
Yes No
คำอธิบาย
วิธีง่ายๆ ในการแก้ปัญหาคือการแก้ปัญหาแต่ละคำถามและค้นหาช่วงที่องค์ประกอบอยู่ หากอยู่ในช่วงใดช่วงหนึ่งให้คืนค่า จริง ไม่เช่นนั้น ให้คืนค่าเท็จ การจัดเรียงเมทริกซ์ตามค่าช่วงสามารถช่วยได้
อัลกอริทึม
ขั้นตอนที่ 1 − จัดเรียงเมทริกซ์ rowise เช่น ตามช่วง
ขั้นตอนที่ 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
