90
правок
Изменения
→Доказательство корректности алгоритма
==Доказательство корректности алгоритма==
Докажем, что полученный нашим алгоритмом лист является отпимальной перестановкой работ.
{{Лемма
|id=lemma1
|about=1
|statement= Если для каких работ <tex> i </tex> и <tex> j </tex> из листа <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) < \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в листе <tex> T </tex> раньше, чем <tex> j </tex>
|proof=
Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.
То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </tex>. Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leq p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже( в силу нашего построения), чем работа <tex> i </tex>, то лемма доказана.
}}
==Псевдокод==
