16. óra
Az OKTV 2. forduló 4. feladat megbeszélése és megoldása a Kömal fórumon találtak alapján.
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!)
"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.)
"