Задача о составлении расписания
Дано расписание уроков со временем начала и временем окончания.
| Предмет | Начало | Окончание |
|---|---|---|
| Математика | 9:00 | 10:30 |
| Русский язык | 9:30 | 10:30 |
| Химия | 10:00 | 11:00 |
Выберите как можно больше уроков так, чтобы их время не пересекалось. Вместо уроков могут быть любые временные промежутки.
Решение
Решение основано на принципе жадных алгоритмов. На каждой итерации выбираем отрезок времени с минимальным временем завершения. В конечном итоге это приводит к тому, что количество выбранных отрезков времени будет наибольшим.
Ссылки
- Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 8. Жадные алгоритмы. Задача составления расписания