Giả sử chúng ta có n điểm trên trục x và danh sách phép tịnh tiến giữa các điểm. Tìm xem liệu có thể đạt đến điểm cuối cùng chỉ từ điểm bắt đầu thông qua các giao dịch này hay không. Vì vậy, nếu có một phép tịnh tiến giữa các điểm x1 và x2, thì chúng ta có thể di chuyển từ điểm x đến bất kỳ điểm trung gian nào giữa x1 và x2, hoặc trực tiếp đến x2. Vì vậy, nếu n =5. Và các giao dịch là 0 đến 2, 2 đến 4, và 3 đến 5. Khi đó đầu ra sẽ là CÓ. Có một đường dẫn từ 0 → 2 → 3 → 5.
Chúng ta phải sắp xếp danh sách theo phần tử đầu tiên của các cặp. Sau đó, bắt đầu từ cặp thứ hai của danh sách và kiểm tra xem phần tử đầu tiên của cặp có nằm giữa phần tử thứ hai của cặp trước đó và phần tử thứ hai của cặp hiện tại hay không. Điều kiện này được sử dụng để kiểm tra xem có một đường dẫn giữa hai cặp liên tiếp hay không. Ở phần cuối, chúng ta sẽ kiểm tra xem điểm chúng ta đã đến có phải là điểm đích hay không và điểm chúng ta đã bắt đầu có phải là điểm xuất phát hay không. Nếu vậy, hiển thị CÓ nếu không, hiển thị KHÔNG.
Ví dụ
#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";
} Đầu ra
Path has found