Задача про директора и график смен программистов

Логическая задача на метод исключения. Разбираемся с репетитором.

Roungroat/ Rawpixel / Annie для Skillbox

Александр Бабаскин

Автор статей о программировании. Изучает Python, разбирает сложные термины и объясняет их на пальцах новичкам. Если что-то непонятно — возможно, вы ещё не прочли его следующую публикацию.

Анна Никитина

Преподаватель математики, автор YouTube-канала «Математика с Аней» и соавтор учебников и методических рекомендаций к учебникам по математике.

Анна готовит учеников к ЕГЭ в школе «Топскул» и консультирует онлайн-школы по вопросам эффективного обучения.

Условие

Директор IT-стартапа нанял пятерых программистов, которые поочерёдно обслуживают проект по графику 2/8 — два дня кодят и восемь отдыхают. Когда программисты не заняты в проекте, они работают по найму в других компаниях.

Из-за разногласий с заказчиком директор ненадолго приостановил проект, а когда всё утряслось, возобновил разработку. До дедлайна всего месяц, и, чтобы уложиться в срок, каждый день один человек должен присутствовать на работе. Перенести дедлайн нельзя, выпустить в один день двух и более работников — тоже. Программисты согласились продолжать сотрудничество с компанией, однако у них есть обязательства перед другими заказчиками и свободны не все дни.

По просьбе директора каждый разработчик прислал даты, в которые он может выйти на смену:

Первый программист: 14–15-е.
Второй программист: 10–11-е или 16–17-е.
Третий программист: 12–13-е или 18–19-е.
Четвёртый программист: 12–13-е или 16–17-е.
Пятый программист: 10–11-е или 14–15-е.

Помогите директору построить график так, чтобы вовремя сдать проект.

Подсказка

Метод исключения подходит для логических задач с большим количеством данных и простыми процессами — когда проще проверить несколько вариантов и исключить неправильные, чем искать алгоритм решения всей задачи. Для удобства все данные можно визуализировать в виде таблицы: представить исходные условия и последовательно отметить каждое изменение.

В нашем случае можно занести в общую таблицу графики всех программистов и подумать, какие временные промежутки оставить или убрать.

Решение

Шаг №1. Перенесём данные из условия задачи в таблицу и отметим дни, в которые каждый из пяти программистов может выйти на работу. Дни удобно сбиваются в пары, поэтому таблицу можно упростить. Сделаем 5 столбцов вместо 10:

Шаг №2. Начинаем постепенно перекрашивать ячейки в зелёный и красный цвета:

Зелёным мы отметим дни, в которые программист выйдет на смену.
Красный будет отвечать за дни, которые мы исключим из рабочего графика.

Первый программист может отработать только с 14-го по 15-е число. Поскольку другой возможности поработать у первого программиста нет, отдаём смены 14-го и 15-го числа ему:

Шаг №3. Переключаемся на пятого программиста, у которого после предыдущего исключения остался только один свободный промежуток — 10-е и 11-е число:

Шаг №4. Теперь мы видим, что 18-го и 19-го числа у нас свободен только третий программист:

Шаг №5. У второго программиста остался единственный слот 16-го и 17-го числа:

Шаг №6. По остаточному принципу закрепляем за четвёртым программистом 12-е и 13-е число и заканчиваем формировать график:

Ответ

По новому графику программисты выйдут на смену в следующие даты: первый — 14–15-го; второй — 16–17-го; третий — 18–19-го; четвёртый — 12–13-го; пятый — 10–11-го.