ตรวจสอบว่าสามารถไปถึงจุดสิ้นสุดได้หรือไม่จากการเปลี่ยนผ่านที่กำหนด (C++)

มีจุดบนแกน x จำนวน n จุด และมีรายการการเปลี่ยนผ่าน (Transitions) ที่อนุญาตระหว่างจุด หากมีการเปลี่ยนผ่านจาก x1 ไป x2 สามารถเคลื่อนที่ไปจุดกลางระหว่าง x1 ถึง x2 หรือไป x2 โดยตรงได้

ตัวอย่าง: n = 5, Transitions: (0,2), (2,4), (3,5) → สามารถไปถึงได้ (0→2→3→5) คำตอบ: YES

อัลกอริทึม

1. จัดเรียงคู่ตามค่าแรก (first element)
2. เริ่มจากคู่ที่สอง ตรวจสอบว่า first ของคู่ปัจจุบันอยู่ระหว่าง second ของคู่ก่อนหน้าและ second ของคู่ปัจจุบันหรือไม่
3. อัปเดต end_point เป็นค่าสูงสุด
4. ท้ายสุดตรวจสอบว่า end_point ≥ n และ start_point = 0

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

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

bool isPathPairFound(int n, vector> array) {
    sort(array.begin(), array.end());

    int start_point = array[0].first;
    int end_point = array[0].second;

    for (int i = 1; i < n; i++) {
        if (array[i].first > end_point)
            break;
        end_point = max(end_point, array[i].second);
    }

    return (n <= end_point && start_point == 0);
}

int main() {
    vector> array;
    array.push_back(make_pair(0, 2));
    array.push_back(make_pair(2, 4));
    array.push_back(make_pair(3, 5));

    if (isPathPairFound(5, array))
        cout << "Path has found";
    else
        cout << "NO Path has found";

    return 0;
}

ผลลัพธ์

Path has found