264
правки
Изменения
→Псевдокод
* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в <tex>d[i] </tex> {{---}} дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения.
'''function''' <tex> \mathrm{getAnswer}(p : </tex> '''int''' <tex>[n],</tex> <tex> w : </tex> '''int''' <tex>[n],</tex> <tex> d : </tex> '''int''' <tex>[n] ):</tex> '''int'''
'''int''' <tex>T = 0 </tex>
'''for''' <tex>i = 1 .. n</tex>
<tex>T = T + p[i]</tex>
'''int''' <tex>F[][]</tex>
сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex>;
'''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
'''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ <tex>L</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
'''function''' <tex> \mathrm{getLate}(F : </tex> '''int''' <tex>[n][p_{max}],</tex> <tex> p : </tex> '''int''' <tex>[n],</tex> <tex> w : </tex> '''int''' <tex>[n],</tex> <tex> d : </tex> '''int''' <tex>[n] ):</tex> '''set<int>'''
'''int''' <tex>t = d[n]</tex>
'''set<int>''' <tex>L = \varnothing</tex>
