หา Range ที่ครอบคลุม Range อื่นๆ ทั้งหมดใน C++

มี N 範圍 (Ranges) แต่ละอันมีค่า L และ R หา Index (0-based) ของ Range ที่ครอบคลุม Range อื่นๆ ทั้ง N-1 อัน หากไม่มีให้คืน -1

ตัวอย่าง: L = [2, 4, 3, 1], R = [4, 6, 7, 9] → Output = 3 (Range index 3 คือ [1,9] ครอบคลุมทุกอัน)

ข้อสังเกตสำคัญ

เนื่องจากค่า L และ R ทั้งหมดไม่ซ้ำกัน หา Range ที่มี L น้อยที่สุดและ R มากที่สุด หากทั้งสองเป็น Range เดียวกัน แสดงว่าครอบคลุมทั้งหมด มิฉะนั้นเป็นไปไม่ได้

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findCoveringRange(vector& L, vector& R) {
    int n = L.size();
    int minL = *min_element(L.begin(), L.end());
    int maxR = *max_element(R.begin(), R.end());

    for (int i = 0; i < n; i++) {
        if (L[i] == minL && R[i] == maxR)
            return i;
    }
    return -1;
}

int main() {
    vector L = {2, 4, 3, 1};
    vector R = {4, 6, 7, 9};

    int idx = findCoveringRange(L, R);
    if (idx != -1)
        cout << "Range at index " << idx << " covers all others: [" << L[idx] << ", " << R[idx] << "]";
    else
        cout << "No such range exists";

    return 0;
}

ผลลัพธ์

Range at index 3 covers all others: [1, 9]

หมายเหตุ

โค้ดต้นฉบับมีฟังก์ชัน fact และ showRange ที่ไม่เกี่ยวข้องกับโจทย์ เราเขียนใหม่ให้ตรงกับโจทย์จริง