สมมติว่าเรามี n จุดบนแกน x และรายการการแปลที่อนุญาตระหว่างจุดต่างๆ ค้นหาว่าเป็นไปได้ที่จะถึงจุดสิ้นสุดจากจุดเริ่มต้นผ่านธุรกรรมเหล่านี้เท่านั้น ดังนั้นหากมีการแปลระหว่างจุด x1 และ x2 เราก็สามารถย้ายจากจุด x ไปยังจุดกลางใดๆ ระหว่าง x1 และ x2 หรือโดยตรงไปที่ x2 ดังนั้นถ้า n =5 และธุรกรรมคือ 0 ถึง 2, 2 ถึง 4 และ 3 ถึง 5 ผลลัพธ์จะเป็น YES มีเส้นทางตั้งแต่ 0→2→3→5
เราต้องเรียงลำดับรายการตามองค์ประกอบแรกของคู่ จากนั้นเริ่มจากคู่ที่สองของรายการและตรวจสอบว่าองค์ประกอบแรกของคู่อยู่ระหว่างองค์ประกอบที่สองของคู่ก่อนหน้าและองค์ประกอบที่สองของคู่ปัจจุบันหรือไม่ เงื่อนไขนี้ใช้เพื่อตรวจสอบว่ามีเส้นทางระหว่างสองคู่ที่ต่อเนื่องกันหรือไม่ ในตอนท้ายเราจะตรวจสอบว่าจุดที่เราไปถึงคือจุดปลายทางหรือไม่และจุดเริ่มต้นที่เราได้เริ่มต้นคือจุดเริ่มต้น ถ้าใช่ ให้แสดง YES มิฉะนั้น ให้แสดง NO
ตัวอย่าง
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool isPathPairFound(int n, vector<pair<int, int> > 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<pair<int, int> > 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";
} ผลลัพธ์
Path has found
