Cho n điểm trên trục Ox và danh sách các đoạn cho phép di chuyển (từ x1 đến x2). Xác định có thể đi từ điểm 0 đến điểm n chỉ dùng các đoạn này không. Có thể dừng ở các điểm trung gian trong đoạn.
Sắp xếp các đoạn theo đầu nhỏ. Duyệt từ đoạn thứ 2, nếu đầu đoạn hiện tại > cuối đoạn trước → đứt đường. Cập nhật cuối = max(cũ, cuối hiện tại). Cuối cùng kiểm tra điểm n có ≤ cuối và điểm bắt đầu = 0.
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";
}
Kết quả
Path has found