Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1459

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1459

Focus

 

Maratona de Programação da SBC Brazil

Timelimit: 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 ≤ AB ≤ 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
1 3
2 5
4 6
5
1 2
5 6
3 4
5 6
1 2

2
3

 

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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 3
2 5
4 6
5
1 2
5 6
3 4
5 6
1 2

Output

x
+
cmd
2
3
Advertisements

Demonstration


Previous
#1441 Beecrowd Online Judge Solution 1441 Hailstone Sequences Solution in C, C++, Java, Js and Python
Next
#1460 Beecrowd Online Judge Solution 1460 Grapevine Solution in C, C++, Java, Js and Python