Algorithm
Pig is visiting a friend.
Pig's house is located at point 0, and his friend's house is located at point m on an axis.
Pig can use teleports to move along the axis.
To use a teleport, Pig should come to a certain point (where the teleport is located) and choose where to move: for each teleport there is the rightmost point it can move Pig to, this point is known as the limit of the teleport.
Formally, a teleport located at point x with limit y can move Pig from point x to any point within the segment [x; y], including the bounds.
Determine if Pig can visit the friend using teleports only, or he should use his car.
The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of teleports and the location of the friend's house.
The next n lines contain information about teleports.
The i-th of these lines contains two integers ai and bi (0 ≤ ai ≤ bi ≤ m), where ai is the location of the i-th teleport, and bi is its limit.
It is guaranteed that ai ≥ ai - 1 for every i (2 ≤ i ≤ n).
Print "YES" if there is a path from Pig's house to his friend's house that uses only teleports, and "NO" otherwise.
You can print each letter in arbitrary case (upper or lower).
3 5
0 2
2 4
3 5
YES
3 7
0 4
2 5
6 7
NO
The first example is shown on the picture below:
Pig can use the first teleport from his house (point 0) to reach point 2, then using the second teleport go from point 2 to point 3, then using the third teleport go from point 3 to point 5, where his friend lives.
The second example is shown on the picture below:
You can see that there is no path from Pig's house to his friend's house that uses only teleports.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[101];
queue<int> q;
bool vis[101];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a, a + n);
if(a[0].first != 0) {
puts("NO");
return 0;
}
q.push(0);
while(!q.empty()) {
int fr = q.front();
q.pop();
vis[fr] = true;
if(m >= a[fr].first && m <= a[fr].second) {
puts("YES");
return 0;
}
for(int i = 0; i < n; ++i)
if(a[i].first >= a[fr].first && a[i].first <= a[fr].second && !vis[i])
q.push(i);
}
puts("NO");
return 0;
}Input
3 5
Output
Demonstration
Codeforces Solution-Visiting a Friend-Solution in C, C++, Java, Python