Метод сканирующей прямой
Задача "Составление расписания"
Допустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков:
Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.
Требуется провести в классе как можно больше уроков. Как отобрать уроки, чтобы полученный набор оказался самым большим из возможных?
Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:
1. Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.
2. Затем выбирается урок, начинающийся после завершения первого урока. И снова следует выбрать урок, который завершается раньше всех остальных. Он становится вторым уроком в расписании.
Продолжайте действовать по тому же принципу - и вы получите ответ! Давайте попробуем. Рисование заканчивается раньше всех уроков (в 10:00), поэтому мы выбираем именно его. Теперь нужно найти следующий урок, который начинается после 10:00 и завершается раньше остальных. Английский язык отпадает - он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.
Итак, эти три урока должны проводиться в классе.
