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:
-
08:00
—08:15
-
08:20
—09:00
-
08:45
—09:15
-
08:55
—09:15
-
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 struct uri. În cazul nostru,
ne vom folosi de doi vectori: timp
și tip
, cu semnificația:
-
timp[i]
reprezintă momentul celui de-ali
-lea eveniment (evenimentul poate fi o venire sau o plecare de tren); -
tip[i]
reprezintă tipul celui de-ali
-lea eveniment:- dacă
tip[i] = 1
, atunci un tren vine; - altfel, dacă
tip[i] = -1
, atunci un tren pleacă.
- dacă
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;
}
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 1