Почему сортировка задач по времени подчинённых даёт наилучшее решение

В задаче распределения поручений между начальником и подчинёнными ключевым моментом является выбор порядка обработки. Интуитивно кажется, что передавать подчинённым задачи с наименьшим временем выполнения (ai) выгодно, но требуется строгое математическое обоснование. Ниже приведено доказательство методом математической индукции, которое подтверждает: сортировка по возрастанию ai минимизирует максимальное время выполнения Tmax.

Постановка задачи

Имеется n поручений. Для каждого i известны: ai - время выполнения подчинённым, bi - время выполнения начальником. Подчинённые работают параллельно (каждый получает не более одной задачи), начальник выполняет свои задачи последовательно. Цель - минимизировать Tmax = max(время_подчинённых, время_начальника).

Доказательство по индукции

База индукции (n = 1)

Для одной задачи возможны два варианта: поручить подчинённому (Tmax = a1) или выполнить самому (Tmax = b1). Оптимум равен max(a1, b1). Сортировка при одном элементе не имеет смысла, но условие выполняется.

Индуктивное предположение

Пусть для k задач, отсортированных по возрастанию ai (a1 ≤ a2 ≤ … ≤ ak), алгоритм даёт минимальный Tmax.

Индуктивный переход (k → k+1)

Добавим задачу (a_{k+1}, b_{k+1}), причём a_{k+1} - максимальное среди всех a, так как массив отсортирован. Рассмотрим два варианта распределения новой задачи.

• Вариант А: задача выполняется подчинённым. Тогда время подчинённых становится равным a_{k+1} (максимум среди всех ai), а время начальника остаётся суммой bi для остальных k задач. Итог: Tmax = max(a_{k+1}, S), где S - сумма bi для первых k задач.
• Вариант Б: задача выполняется начальником. Время подчинённых равно a_k (максимум среди первых k задач), время начальника увеличивается на b_{k+1}. Итог: Tmax = max(a_k, S + b_{k+1}).

Поскольку a_{k+1} ≥ a_k, вариант А может оказаться хуже, если a_{k+1} слишком велико. Однако сортировка гарантирует, что все предыдущие ai меньше или равны a_{k+1}, поэтому передача подчинённому задачи с наибольшим ai не ухудшает время подчинённых сильнее, чем если бы мы передали задачу с меньшим ai (так как максимум всё равно станет a_{k+1}).

Сравним Tmax для обоих вариантов. Если a_{k+1} ≤ S + b_{k+1}, то вариант А даёт Tmax = max(a_{k+1}, S) ≤ max(a_k, S + b_{k+1}) = Tmax варианта Б (так как a_{k+1} ≥ a_k, но S + b_{k+1} ≥ S). Если же a_{k+1} > S + b_{k+1}, то вариант А даёт Tmax = a_{k+1}, а вариант Б - max(a_k, S + b_{k+1}) < a_{k+1} (так как S + b_{k+1} < a_{k+1}, а a_k ≤ a_{k+1}). В этом случае вариант Б лучше. Но сортировка не мешает выбрать оптимальное распределение: алгоритм на каждом шаге проверяет условие и решает, кому отдать задачу. Ключевой момент - порядок просмотра: если задачи не отсортированы, то при передаче подчинённому задачи с большим ai мы можем получить неоптимальный Tmax из-за того, что не учли возможность отдать её начальнику. Сортировка по возрастанию ai гарантирует, что при проходе слева направо мы всегда сравниваем текущую задачу с уже накопленным временем начальника, и решение принимается корректно.

Практический вывод

Таким образом, сортировка по ai (времени подчинённых) является необходимой для работы жадного алгоритма, который последовательно решает, кому поручить каждую задачу. Без этой сортировки алгоритм может дать неверный результат, так как порядок задач влияет на условие передачи.