tgoop.com/javaproglib/7039
Create:
Last Update:
Last Update:
🔥 Задача на алгоритмы: оптимизация расписания задач
Иногда даже повседневные задачи превращаются в отличный повод вспомнить алгоритмы и потренировать мозг. Особенно если представить, что это часть сервиса планирования нагрузок или распределения вычислений в распределённой системе.
🔹 Условие
— У вас есть N задач, каждая с временем выполнения t[i].
— Есть K воркеров (потоков, серверов), которые могут выполнять задачи параллельно, но каждый воркер может брать только одну задачу за раз.
Нужно распределить задачи между воркерами так, чтобы время завершения всех задач было минимальным.
t = [3, 7, 2, 5, 4]
K = 2
— если раздать задачи просто по очереди, один воркер закончит через 14 секунд, другой — через 7.
— а если распределить умнее (например, [7,3] и [5,4,2]), итоговое время — 10 секунд.
🔹 Уточнения
— N может достигать 10⁴
— K до 100
— Допустимо небольшое отклонение от оптимума (например, ≤5%)
— Требуется O(N log N) или лучше
— Можно предусмотреть балансировку “на лету” при поступлении новых задач
🔹 Вопрос
Какой алгоритм примените для минимизации времени выполнения?
Подумайте о вариантах:
— жадный
— динамическое программирование
— приближённые решения (если N велико)
🔹 Подсказки
—
—
👇🏻 Скелет решения предложили в комментах.
#CoreJava