16. óra
Engedy Balázs - Weisz Ágoston:
"Pedig Ágoston már elmondta a jó megoldást, csupán két irányt felcserélt: az első csoportba kerülnek tehát azok, amelyekre $a_i\leq b_i$, a másodikba pedig az $a_i>b_i$ feltételnek megfelelők. Az első csoportot $a_i$ szerint növekvően, a második csoportot $b_i$-k szerint csökkenően rendezzük, majd a gépeknek sorban beadjuk az első, majd a második csoportba került elemeket, amilyen hamar csak tudjuk. (Vegyük észre a forgási szimmetriát!)
Hogy ne csak kötözködjek, egy kis hint a bizonyításhoz: induljunk ki egy optimális ütemezésből (tehát ahol nem csak a sorrendet, hanem a végrehajtások pontos idejét is tudjuk minden munkadarabra mindkét gépnél), és mutassuk meg, hogy amikor cserékkel az ütemezés elejére rendezzük $a_i$-k szerint növekvő sorrendbe az első csoport elemeit, illetve a végére $b_i$-k szerint csökkenő sorrendbe a második csoportba tartozó munkadarabokat, akkor az áthelyezések során az optimalitási tulajdonság nem sérül, illetve az ütemezés továbbra is legális marad. (És végül eljutunk a fenti algoritmus által előállított ütemezéshez.)
"
TODO: Bizonyítás...
