Нужно собрать максимально «ровную» по уровню команду: чем меньше разница между
максимальным и минимальным уровнем выбранных инженеров, тем лучше. Есть K
функций (бэкенд, фронтенд, QA, дизайн, …), для каждой — отсортированный по
неубыванию список уровней инженеров. Выберите по одному инженеру от каждой
функции так, чтобы max − min уровней команды был минимальным. Если вариантов
несколько, верните любой.
// EvenTeam возвращает team, где team[i] — уровень, взятый из levels[i],
// и max(team) - min(team) минимален. Если хотя бы один список пуст или
// списков нет, возвращает nil.
func EvenTeam(levels [][]int) []int
Примеры
backend=[2,3,3,4], frontend=[2,4], qa=[4,5,5], design=[3,4]
→ [4, 4, 4, 4] (разброс 0)
backend=[7], frontend=[5,8,9,12], qa=[5,11,13,20], design=[22]
→ [7, 8, 11, 22] (разброс 15; [7, 12, 11, 22] тоже верно)
Ограничения
0 ≤ K ≤ 1000, суммарно N ≤ 10⁶ элементов, каждый список отсортирован.- Входные данные не изменять.
- Для K = 4 ожидается O(N) по времени и O(1) доп. памяти; для произвольного K —
O(N·log K). Перебор всех комбинаций не проходит.