Programările care se suprapun

Când se suprapun două consultații

Fiecare consultație începe la o oră fixă și durează 50 de minute, deci se încheie înainte de începerea orei următoare: consultația de la ora 12 durează de la 12:00 până la 12:50, iar cea de la ora 13 începe abia la 13:00. Două consultații programate la ore diferite din aceeași zi nu se suprapun, iar două consultații programate în zile diferite nu se suprapun în niciun caz.

Rezultă că două programări se suprapun dacă și numai dacă au același cod, fiindcă acel cod cuprinde chiar ziua și ora. Problema se reduce astfel la numărarea valorilor care se repetă în șir.

Dintr-un grup de programări cu același cod, una singură poate rămâne neschimbată, iar celelalte trebuie mutate. Un cod care apare de k ori dă deci k−1 programări de actualizat. În exemplul din enunț, codul 912 apare de trei ori, deci două programări se mută, iar codul 1418 apare de două ori, deci încă una: în total 3.

Explicarea metodei de rezolvare

Enunțul precizează că numerele din fișier sunt ordonate crescător. De aici rezultă că valorile egale se află una lângă alta, așa că, pentru a afla dacă o valoare se repetă, este de ajuns să fie comparată cu cea citită imediat înaintea ei. Nu trebuie păstrat tot șirul și nu trebuie căutat prin el.

Numerele se citesc din fișier unul câte unul. Se folosesc două variabile: una care reține valoarea citită anterior și una care numără programările de actualizat. Pentru fiecare valoare nouă se face o singură comparație: dacă este egală cu cea anterioară, contorul crește cu 1, fiindcă valoarea respectivă este a doua, a treia și așa mai departe dintr-un grup, deci programarea ei trebuie mutată; dacă este diferită, contorul rămâne neschimbat, fiindcă ea deschide un grup nou. În amândouă cazurile, valoarea curentă devine valoare anterioară pentru pasul următor.

Numărarea în această formă dă exact suma cerută: dintr-un grup de k valori egale, prima nu este numărată, iar celelalte k−1 sunt, deci contorul adună k−1 pentru fiecare grup.

Prima valoare din fișier nu are predecesor, așa că variabila care reține valoarea anterioară se inițializează cu o valoare aflată în afara intervalului [108, 3120], de exemplu −1. Astfel, prima comparație dă în mod sigur rezultatul fals.

Justificarea eficienței

Din punctul de vedere al timpului. Fișierul este parcurs o singură dată, iar pentru fiecare număr se fac o citire, o comparație și o atribuire. Timpul de executare este deci proporțional cu numărul valorilor din fișier: algoritmul este liniar, O(n), pentru n de cel mult 10⁵. Un ordin de complexitate mai mic nu este posibil, fiindcă orice soluție trebuie să citească toate datele.

Din punctul de vedere al memoriei. Nu se memorează șirul citit. Se rețin doar valoarea curentă, valoarea anterioară și contorul, deci un număr de variabile care nu depinde de n: memoria suplimentară folosită este constantă, O(1).