Truy vấn kiểm tra số có nằm trong N khoảng L-R trong C++

Mô tả bài toán

Cho N khoảng [L, R] (không giao nhau) và Q truy vấn mỗi truy vấn một số. Kiểm tra số đó có nằm trong bất kỳ khoảng nào không.

Ví dụ: khoảng {{5,7},{1,3},{9,12}}, truy vấn {10,4} → Yes, No.

Giải thuật

1. Sắp xếp các khoảng theo L tăng dần.
2. Với mỗi truy vấn, duyệt qua các khoảng (hoặc tìm kiếm nhị phân) để kiểm tra L ≤ x ≤ R.
3. Trả về "Yes" nếu tìm thấy, ngược lại "No".

Ví dụ minh họa (C++)

#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[]) {
    // Sắp xếp khoảng theo L
    for (int j = 0; j < n-1; j++)
        for (int k = j+1; k < n; k++)
            if (arr[j][0] > arr[k][0]) {
                swap(arr[j][0], arr[k][0]);
                swap(arr[j][1], arr[k][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;
}

Đầu ra

For Query 1: The number 10 lies in the range
For Query 2: The number 4 does not lie in the range