Numărul minim de peroane pentru o gară în C++

Știind momentele venirii și plecării ale unor trenuri într-o gară, să se determine numărul minim de peroane pe care trebuie să le aibă gara pentru ca fiecare tren să poată să staționeze.

Exemplu: Să presupunem că vin n = 5 trenuri la orele:

1. 08:00 — 08:15
2. 08:20 — 09:00
3. 08:45 — 09:15
4. 08:55 — 09:15
5. 09:20 — 09:25

Atunci, sunt necesare minimum trei peroane pentru ca toate trenurile să poată staționa la gară (în intervalul 08:55 — 09:00, vor fi trei trenuri în gară simultan).

Pentru datele de intrare, vom citi:

5
800 815
820 900
845 915
855 915
920 925

Explicarea algoritmului

Problema noastră se reduce la a ne asigura că în momentul în care un număr maxim de trenuri sunt în gară, toate acestea au un loc de staționare asigurat. În exemplul nostru, trebuia să ne asigurăm că sunt minimum trei peroane, pentru a asigura staționarea trenurilor 2, 3 și 4 în intervalul 08:55 — 09:00. Putem observa intervalul în imaginea de mai jos (cu roșu este intervalul căutat):

Cum găsim intervalul de timp în care sunt cele mai multe trenuri în gară?

Să contorizăm numărul de trenuri din gară. La început, sunt 0 trenuri. După venirea primului tren, va fi 1 tren. La plecarea acestuia, vor fi iarăși 0 trenuri. Când vine trenul al doilea, iarăși va fi 1 tren. Când vine al treilea tren, vor fi 2 trenuri. Când vine al patrulea tren, vor fi 3 trenuri (maximul). Și așa mai departe.

Observăm că, dacă ordonăm momentele venirii și plecării în ordine cronologică și considerăm momentele venirii +1 și cele de plecare -1, numărul maxim de trenuri în gară este maximul dintre valorile contorului pe parcursul parcurgerii momentelor. În exemplu, contorul ia valorile 0, 1, 0, 1, 2, 3, 2, 1, 0, 1, 0, maximul lor fiind 3.

Cum ordonăm momentele de venire și de plecare?

Există multe metode, cele mai elegante folosind structuri. În cazul nostru, ne vom folosi de doi vectori: timp și tip, cu semnificația:

• timp[i] reprezintă momentul celui de-al i-lea eveniment (evenimentul poate fi o venire sau o plecare de tren);
• tip[i] reprezintă tipul celui de-al i-lea eveniment:
  • dacă tip[i] = 1, atunci un tren vine;
  • altfel, dacă tip[i] = -1, atunci un tren pleacă.

După ce citim aceste date, le vom sorta folosind un algoritm de sortare cunoscut. După care, folosind observația de mai devreme, putem să calculăm contorul și să luăm cea mai mare valoare posibilă.

Rezolvare în C++

Iată rezolvarea în C++, fără să folosim structuri:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim
    int n; //numărul de trenuri
    int timp[101]; //timpul în care vin trenurile
    int tip[101]; //tipurile trenurilor
    int nrev = 0; //numărul evenimentelor; pentru fiecare dintre cele n trenuri sunt 2 evenimente, așadar nrev = 2 * n după citire
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int venire, plecare;
        cin >> venire >> plecare;
        //Băgăm evenimentul de venire
        nrev++;
        timp[nrev] = venire;
        tip[nrev] = 1;

        //Băgăm evenimentul de plecare
        nrev++;
        timp[nrev] = plecare;
        tip[nrev] = -1;
    }

    //Sortăm evenimentele în ordine cronologică (adică în funcție de *timp*)
    //Avem grijă să interschimbăm atât valorile din timp, cât și din tip
    for(int i = 1; i <= nrev; i++) {
        for(int j = i + 1; j <= nrev; j++) {
            if(timp[i] > timp[j]) {
                int aux = timp[i];
                timp[i] = timp[j];
                timp[j] = aux;
                aux = tip[i];
                tip[i] = tip[j];
                tip[j] = aux;
            }
        }
    }

    //În acest moment, evenimentele sunt în ordine cronologică
    //Parcurgem evenimentele pe rând și contorizăm, luând maximul
    //Observăm că nu ne mai trebuie timpul, ci doar tipul evenimentelor
    int contor = 0, raspuns = 0;
    for(int i = 1; i <= nrev; i++) {
        contor += tip[i]; //contor crește sau scade cu 1
        if(contor > raspuns) { //actualizăm răspunsul dacă contorul are o valoare maximă nouă
            raspuns = contor;
        }
    }
    cout << raspuns;
    return 0;
}