সি++-এ নম্বর নির্দিষ্ট রেঞ্জে আছে কিনা যাচাই করার কোয়েরি সমাধান

সমস্যা বিবরণ

একটি ২D ম্যাট্রিক্স arr[][2] দেওয়া আছে যাতে nটি রেঞ্জ [L, R] রয়েছে। Qটি কোয়েরি আছে, প্রতিটিতে একটি ইন্টিজার। চেক করতে হবে কোয়েরির সংখ্যাটি কোথাও রেঞ্জে আছে কিনা। রেঞ্জগুলো ওভারল্যাপ করে না।

উদাহরণ: arr = {{5,7}, {1,3}, {9,12}}, n=3, Q=2, query = {10, 4}

আউটপুট: Yes, No

সমাধানের পদ্ধতি

1. রেঞ্জগুলো стар্টিং পয়েন্ট অনুযায়ী সর্ট করুন।
2. প্রতিটি কোয়েরির জন্য লিনিয়ার সার্চ বা বাইনারি সার্চ করে চেক করুন arr[i][0] <= query <= arr[i][1]।
3. যদি মিল পাওয়া যায় Yes, অন্যথায় No।

উদাহরণ কোড

#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, 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