1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Постановка задачи==
Дан один станок на котором нужно выполнить <tex>n</tex> работ. Для каждой работы известны моменты времени, когда можно начинать её выполнять - <tex>r_{i}</tex> и когда необходимо закончить её выполнение - <tex>d_{i}</tex>. Время выполнение выполнения <tex>p_{i}</tex> у всех работ одинаково и равно одному. Необходимо узнать, можно ли построить расписание для этого станка.
==Алгоритм==
<tex>END</tex>
<tex>END</tex>
Сложность алгоритма <tex>O(n\log n)</tex> если в качестве <tex>S</tex> использовать структуру, которая позволяет поиск элемента с минимальным <tex>d_{i}</tex> за <tex>O(\log n)</tex>.
==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
