Programozás‎ > ‎Feladatok‎ > ‎Vasúti menetrend‎ > ‎

Megoldás

Algoritmus

Mindkét állomáshoz létrehozunk egy-egy prioritási sort, amelyben azt tároljuk, hogy az adott állomáson hány vonat és mikor fog rendelkezésre állni. A prioritási sor rendezési kulcsa az az időpont, amikor az adott vonat leghamarabb el tud indulni az adott állomásról. Kezdetben mindkét sor üres.

A menetrend elemein indulási idő szerinti sorrendben megyünk végig.
  • Ha az adott járat az X állomásról T időpontban indul, és az X állomás sorában a legkorábban elérhető vonat el tud indulni ekkor, akkor ez a járat rendben van, a vonat pedig átkerül a másik állomás sorába. Új indulási idejét az előző járat érkezési idejéből, és a fordulási időből számíthatjuk ki.
  • Ha pedig az éppen vizsgált járathoz nincs rendelkezésre álló vonat, akkor az indulási állomáson eggyel növeljük a szükséges vonatok számát, és felveszünk egy új vonatot (célszerűen már a célállomás sorába).
Végül összeadjuk a két állomásnál számolt szükséges vonatok számát.

Kódok

Lipták Bence (pascal): lb_vasut.pas
Mikó Péter (pascal): mp_menetrend.pas
Ódor Gergő (C++): og_vonat.cpp