Trong bài toán này, chúng ta được đưa ra một ma trận 2-D arr [] [2] bao gồm n dãy (L, R), L-R. Và Q truy vấn mỗi truy vấn bao gồm một giá trị nguyên. 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 hay không.
Mô tả sự cố - Ở đây, chúng tôi giải quyết từng truy vấn sao cho mỗi phần tử của truy vấn nằm trong bất kỳ một trong các phạm vi.
chúng không thể chồng chéo các phạm vi.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[n][2] = { {5, 7}, {1, 3}, {9, 12} } n = 3 Q = 2, query = {10, 4} Đầu ra
Yes No
Giải thích
Một cách đơn giản để giải quyết vấn đề là giải quyết từng truy vấn và tìm phạm vi mà các phần tử nằm trong đó. Nếu nó nằm trong bất kỳ một trong phạm vi nào thì trả về true, ngược lại thì trả về false. Sắp xếp ma trận dựa trên các giá trị phạm vi có thể hữu ích.
Thuật toán
Bước 1 - Sắp xếp ma trận theo chiều ngược lại, tức là dựa trên phạm vi.
Bước 2 - Vòng lặp cho i -> 0 đến Q, cho tất cả các truy vấn.
Bước 2.1 - nếu phần tử nằm trong bất kỳ dải ô nào, tức là (arr [i] [0] <=q &&arr [i] [1]> =q) -> trả về true.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
For Query 1: The number 10 lies in the range For Query 2: The number 4 does not lie in the range