Cerința

Se consideră un șir de n intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă.

Să se determine câte intervale există în șir după realizarea acestor operații.

Date de intrare

Fișierul de intrare intervale4.in conține pe prima linie numărul n, iar următoarele n linii câte două valori x y, reprezentând intervalele inițiale, în ordine.

Date de ieșire

Fișierul de ieșire intervale4.out va conține pe prima linie numărul C de intervale din șir, după realizarea operațiilor.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• pentru fiecare interval dat, x ≤ y

Exemplu

intervale4.in

5
2 3
4 6
3 5
8 10
7 11

intervale4.out

2

Explicație

Intervalele din șirul inițial sunt: [2,3] [4,6] [3,5] [8,10] [7,11].

1. Se reunesc intervalele [4,6] [3,5] și se obține șirul [2,3] [3,6] [8,10] [7,11].
2. Se reunesc intervalele [2,3] [3,6] și se obține șirul [2,6] [8,10] [7,11].
3. Se reunesc intervalele [8,10] [7,11] și se obține șirul [2,6] [7,11].

La final în șir se află două intervale.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("intervale4.in");
ofstream cout("intervale4.out");

struct perechi{
    int x , y;
};

perechi a[100001];

bool intersectie(int i)
{
    return !(a[i].x > a[i-1].y || a[i].y < a[i-1].x);
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i].x >> a[i].y;
        while(i > 1 && intersectie(i))
        {
            a[i-1].x = min(a[i].x , a[i-1].x);
            a[i-1].y = max(a[i].y , a[i-1].y);
            i--;
            n--;
        }
    }
    cout << n;
    return 0;
}