Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1459
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1459
Focus
BrazilTimelimit: 3
Daniel is taking a Computacional Vision course and decided to reproduce an interesting work that he saw at class: he took some photos of a same scene, varying just the focus, for later to combine them in just one photo, in which all the objects in scene are clear together. For that, he needs that each object seem clearly in at least one photo.
Daniel knows that for each object, there is a closed interval of focus plans in which that object stays clearly visible. For example, in the picture below, (i), (ii) and (iii) are tree photos of the same scene, each one taken with a different focus; (iv) is the combined image generated by Daniel.
As the memory card of Daniel's camera has a small capacity, he asked for your help. Given the intervals of focus of all the objects in the scene that he pretends to photograph, determine the minimum number of photos that he should take so that each object stays clear in at least one of the pictures.
Input
The input consists in several case tests. The first line of each test case contains one integer N (1 ≤ N ≤ 106 ) that indicates the number of objects in the scene. Each one of the N next lines contains two integers, A and B (1 ≤ A ≤ B ≤ 109), that indicates the extremes of the focus interval of each object.
Output
For each test case, you should print one line with a integer that indicates the minimum number of photos that Daniel have to take.
| Sample Input | Sample Output |
|
3 |
2 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <iostream>
#include <vector>
#define mp make_pair
using namespace std;
typedef pair < int, int> ii;
int main()
{
ios::sync_with_stdio(false);
int a;
while (cin >> a) {
int x1, x2;
vector < ii> atrac;
vector<ii>::iterator it;
for (int i = 0; i < a; ++i) {
cin >> x1 >> x2;
atrac.push_back(mp(x2, x1));
}
sort(atrac.begin(), atrac.end());
it = atrac.begin();
int sum = 0;
while (it != atrac.end()) {
sum++;
int n2 = it->first;
while ((it->second) < = n2 && it != atrac.end())
it++;
}
cout << sum << "\n";
}
return 0;
}
Input
1 3
2 5
4 6
5
1 2
5 6
3 4
5 6
1 2
Output
3