Книга является наиболее полным руководством по разработке эффективных ал

Глава 1. Введение в разработку алгоритмов 
27 
рых равно 
n
. Каждое предложение имеет условие, что вы должны посвятить себя ему с 
первого до последнего дня съемок. Поэтому вы не можете сниматься одновременно в 
фильмах с полностью или частично накладывающимися периодами съемок. 
Ваш критерий для принятия того или иного предложения довольно прост: вы хотите 
заработать как можно больше денег. Поскольку вам платят одинаково за каждый 
фильм, то вы стремитесь получить роли в как можно большем количестве фильмов, 
периоды съемок которых не конфликтуют. 
На рис. 1.5 перечислены фильмы, в которых вам предлагают роли. 
Рис. 1.5. 
Экземпляр задачи планирования непересекающихся календарных периодов 
В данном случае очевидно, что вы можете сниматься, самое большее, в четырех филь-
мах — "Discrete Mathematics", "Programming Challenges", "Calculated Bets", а потом 
в "Halting State" или в "Steiner's Tree". 
А в менее очевидных случаях вам (или вашему менеджеру) нужно будет решить сле-
дующую алгоритмическую задачу календарного планирования: 
ЗАДАЧА.
Планирование съемок в фильмах. 
Вход.
Множество 
I
интервалов времени 
n
в линейном порядке. 
Выход.
Самое большое подмножество непересекающихся интервалов времени, кото-
рое возможно во множестве 
I.
На ум может прийти несколько способов решения этой задачи. Один из них основан на 
представлении, что надо работать всегда, когда это возможно. Это означает, что вам 
нужно брать роль в фильме, съемки которого начинаются раньше всех других. Псевдо-
код этого алгоритма представлен в листинге 1.5. 
Листинг 1.5. Алгоритм первой возможной работы 
EarliestJobFirst(I) 
Из множества фильмов I берем роль в фильме j с самым ранним началом 
съемок, период которых не пересекается с периодом ваших предыдущих 
обязательств. Поступаем таким образом до тех пор, пока больше 
не останется таких фильмов. 
Этот подход выглядит логично, по крайней мере, до тех пор, пока вы не осознаете, что 
хватаясь за самую раннюю работу, можете пропустить несколько других, если первый 
фильм является сериалом. Пример такой ситуации показан на рис. 1.6, 
а
, где самым 
ранним фильмом является киноэпопея "War and Peace", которая закрывает перед вами 
все другие перспективы. 
Этот пример заставляет искать другое решение. Проблема с фильмом "War and Peace" 
заключается в том, что его съемки длятся слишком долго. В таком случае, может быть, 

---

28