🔥 Задача на алгоритмы: оптимизация расписания задач

Иногда даже повседневные задачи превращаются в отличный повод вспомнить алгоритмы и потренировать мозг. Особенно если представить, что это часть сервиса планирования нагрузок или распределения вычислений в распределённой системе.

🔹 Условие

— У вас есть 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)

👇🏻 Скелет решения предложили в комментах.

💬 Делитесь своими решениями: какой алгоритм выбрали бы для продакшена, а какой — для интервью?

🐸 Библиотека джависта

#CoreJava

❓ Нужно ли изучать JDBC, если уже работаешь с ORM?

Наш подписчик спрашивает:

Работаю джуном на проекте на Spring Boot и Hibernate. ORM вроде понятен — есть аннотации, Entity, Repository, всё работает «из коробки». Но недавно на собеседовании спросили, как работает JDBC под капотом, что такое PreparedStatement, и я понял, что знаю это очень поверхностно.

Возникает вопрос — стоит ли вообще углубляться в JDBC, если в проектах всё делается через ORM? Или это знания “для галочки”?

🔹 Что думаете?

Нужно ли джуну копать в сторону JDBC и понимать, как Hibernate общается с базой? Или достаточно знать ORM-уровень и двигаться дальше — в кэширование, оптимизацию запросов и т.п.?

💬 Делитесь опытом:

— В каких кейсах применяете JDBC
— Насколько часто ORM «прячут» ошибки, которые проще понять через нативный SQL
— Что посоветуете джунам: когда стоит спуститься на уровень JDBC и зачем это вообще нужно

🐸 Библиотека джависта

#DevLife