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

intervale4.out

Explicație

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

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

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Intervale4:

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("intervale4.in");
ofstream fout("intervale4.out");

int A[100005] , B[100005] , n , nrs;

bool Intersectie(int a , int b , int x , int y)
{
    //verificam daca intervalul [a,b] si intervalul [x,y] au intersectia nevida
    if(a <= x && x <= b)
        return true;
    if(a <= y && y <= b)
        return true;
    if(x <= a && a <= y)
        return true;
    if(x <= b && b <= y)
        return true;
    return false;
}

int main()
{
    fin >> n;
    nrs = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        nrs ++;
        fin >> A[nrs] >> B[nrs];
        while(nrs > 1 && Intersectie(A[nrs-1] , B[nrs-1] , A[nrs] , B[nrs]))
        {
            if(A[nrs-1] > A[nrs])
                A[nrs-1] = A[nrs];
            if(B[nrs-1] < B[nrs])
                B[nrs-1] = B[nrs];
            nrs --;
        }
    }
    fout << nrs << "
";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #878 Intervale4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #878 Intervale4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #878 Intervale4