🔥 Задача на алгоритмы: оптимизация расписания задач
Иногда даже повседневные задачи превращаются в отличный повод вспомнить алгоритмы и потренировать мозг. Особенно если представить, что это часть сервиса планирования нагрузок или распределения вычислений в распределённой системе.
🔹 Условие
— У вас есть 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 велико)
🔹 Подсказки
— Это классическая NP-трудная задача разбиения множества (Partition Problem)
— На практике часто решается жадным алгоритмом LPT (Longest Processing Time first)
👇🏻 Скелет решения предложили в комментах.
💬 Делитесь своими решениями: какой алгоритм выбрали бы для продакшена, а какой — для интервью?
🔥 Задача на алгоритмы: оптимизация расписания задач
Иногда даже повседневные задачи превращаются в отличный повод вспомнить алгоритмы и потренировать мозг. Особенно если представить, что это часть сервиса планирования нагрузок или распределения вычислений в распределённой системе.
🔹 Условие
— У вас есть 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 велико)
🔹 Подсказки
— Это классическая NP-трудная задача разбиения множества (Partition Problem)
— На практике часто решается жадным алгоритмом LPT (Longest Processing Time first)
👇🏻 Скелет решения предложили в комментах.
💬 Делитесь своими решениями: какой алгоритм выбрали бы для продакшена, а какой — для интервью?
In 2018, Telegram’s audience reached 200 million people, with 500,000 new users joining the messenger every day. It was launched for iOS on 14 August 2013 and Android on 20 October 2013. Find your optimal posting schedule and stick to it. The peak posting times include 8 am, 6 pm, and 8 pm on social media. Try to publish serious stuff in the morning and leave less demanding content later in the day. A few years ago, you had to use a special bot to run a poll on Telegram. Now you can easily do that yourself in two clicks. Hit the Menu icon and select “Create Poll.” Write your question and add up to 10 options. Running polls is a powerful strategy for getting feedback from your audience. If you’re considering the possibility of modifying your channel in any way, be sure to ask your subscribers’ opinions first. Those being doxxed include outgoing Chief Executive Carrie Lam Cheng Yuet-ngor, Chung and police assistant commissioner Joe Chan Tung, who heads police's cyber security and technology crime bureau. Informative
from us
