ตรวจสอบตัวเลขอยู่ในช่วง L-R ใดช่วงหนึ่งหรือไม่ใน C++

ภาพรวมปัญหา

ได้รับ N ช่วง [L, R] และ Q คำถาม แต่ละคำถามมีค่า val ตรวจสอบว่า val อยู่ในช่วงใดช่วงหนึ่งหรือไม่

ตัวอย่าง

Ranges: {2,4}, {6,7}, {9,12}
Queries: 1, 7, 10
Output: Not Present, Present, Present

แนวทางแก้ปัญหา

• เก็บ L และ R ทั้งหมดใน Vector แล้ว Sort
• ใช้ HashMap บันทึกว่าแต่ละค่าเป็น L (ค่า 1) หรือ R (ค่า 2)
• ใช้ Binary Search (lower_bound) หาตำแหน่งของ val
• ถ้าตำแหน่งเป็น R -> อยู่ในช่วง, ถ้าเป็น L -> ไม่อยู่ในช่วง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

vector v;
unordered_map mpp;

void initialiseMap(int a[][2], int n) {
    for (int i = 0; i < n; i++) {
        v.push_back(a[i][0]); mpp[a[i][0]] = 1;
        v.push_back(a[i][1]); mpp[a[i][1]] = 2;
    }
    sort(v.begin(), v.end());
}

bool isElementPresent(int val) {
    int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
    if (v[ind] == val) return true;
    return mpp[v[ind]] == 2;
}

int main() {
    int arr[][2] = {{2,4}, {6,7}, {9,12}};
    initialiseMap(arr, 3);
    int query[] = {1, 7, 10};
    for (int i = 0; i < 3; i++) {
        if (isElementPresent(query[i])) cout << "Present\n";
        else cout << "Not Present\n";
    }
    return 0;
}

ผลลัพธ์

Not Present
Present
Present